Time Limit: 3 sec
Memory Limit: 32 MB
Your friend John was told to find an ingeter solution to the equation:
x1 + 2 x2 + 4 x3 + 8 x4 = 15 where xi ≥ 0
John spent all week thinking and could find only one solution, it is x1=1; x2=1; x3=1; x4=1. However, he thinks that is not the only possible integer solution to this equation, but he isn’t sure about it. You have decided to help your friend to prove or deny his assumption. In order to do this you should write a program that finds the number of integer solutions for a given equation (let us leave the fun of searching solutions to John). On the other hand it is rather boring to write program for this particular equation, so you generalize it into the form:
x1 + 2 x2 + 4 x3 + 8 x4 + 16 x5 + ... + 2t xt= K where xi ≥ 0 .
Can you manage this?
The number of tests T (T ≤ 105) is given on the first line. Each of next T lines contains two numbers K M (0 ≤ K ≤ 105; 1 ≤ M ≤ 1015). Where K is the number from equation and M is modulo. M can be always factorized into primes numbers not larger than 150.
For each test case output a single line "Case T: N". Where T is the test case number (starting from 1) and N is the number of different integer vectors that are solutions to a given equation. As number N can be very large, output it modulo M.
3 15 99 101 123 1234 536870912
Case 1: 26 Case 2: 111 Case 3: 176223474