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.