_{This problem is a programming version of Problem 219 from projecteuler.net}

Let and be bit strings (sequences of and ).

If is equal to the leftmost bits of , then is said to be a prefix of .

For example, is a prefix of , but not of or .

A prefix-free code of size is a collection of distinct bit strings such that no string is a prefix of any other. For example, this is a prefix-free code of size :

- , , , , ,

Now suppose that it costs one penny to transmit a bit, but pence to transmit a .

Then the total cost of the prefix-free code shown above is pence, which happens to be the cheapest possible for the skewed pricing scheme in question.

In short, we write .

Given several tuples of numbers find the total cost of the cheapest prefix-free code of size with costs and of transmission bit and bit respectively.

Calculate the result modulo ().

**Input Format**

First line of each test file contains a single integer that is the number of tuples. Then lines follow, each containing three integers: , and size of prefix-free code, cost of and cost of .

**Constraints**

**Output Format**

Print exactly lines with a single integer on each: an answer to the corresponding query modulo .

**Sample Input 0**

```
2
6 1 4
9 1 1
```

**Sample Output 0**

```
35
29
```

**Explanation 0**

The first prefix-free code is the following:

, , , , ,

Its cost is

The second prefix-free code is the following:

, , , , , , , ,

Its cost is . This code is not unique.