Tuco Salamanca is one dangerous guy as we all know. One day Heisenberg and Jesse were trapped inside his house. They were unable to get out of his house.
The DEA gets to know about a hint of their location. To get the location, they need to solve the given problem.
Given a polynomial p(x) of degree n. Let's define P(x) = p(x) power N. That means p(x) multiplied N times. Let's say C(i) denote the coefficient of xi in P(x).
Now you need to answer Q queries of the following form:-
Given an integer d which is power of 2. Compute the sum of coefficients C(jxd) of P for all integer j such that (0 < j x d ≤ degreeOfP). Since the answer can be huge, you need to print only the answer modulo 114689. Please note that it is a prime number.
Can you help them out?
INPUT
OUTPUT
CONSTRAINTS
Given polynomial p(x) = 0 + x + 2x2 and exponent N = 3
Hence, P(x) = p(x)3 = 0 + 0x + 0x2 + 1x3 + 6x4 + 12x5 + 8x6
For first query we need to sum coefficients of x 1, x2 ... x6. That is 0 + 0 + 1 + 6 + 12 + 8 which is equal to 27.
For second query we need to sum coefficients of x2, x4 and x6. That is 0 + 6 + 8 which is equal to 14.
For third query we need coefficients of x4 only. That is 6.