Project Euler #219: Skew-cost coding

_{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.