1s, 512 MB
Given a degree polynomial () and , find for a given number .
I found this problem in an online contest. But it was very tough for me to solve. Luckily I found a solution pattern for this problem generating solution for some small test cases. I found that:
But still, I can't find . So please help me out.
The first line contains a single integer () number of test cases. On next line there are numbers, () meaning that in case you should solve for number .
For each test case , print the answer modulo on separate lines.
1 2 3 4
for the second test case :
$f(0)=1$ because there is only one polynomial for which
$P(2)=0$ and the polynomial is
$f(1)=1$ because there is only one polynomial for which
$P(2)=1$ and the polynomial is
$f(2)=2$ because there is two such polynomial for which
$P(2)=2$ and the polynomials are
$P(x)=2\times x^0$ and
$P(x)=0\times x^0+1\times x^1$
Here means . means “largest integer which is smaller than or equal to x".