Fibonacci Wars II
All submissions for this problem are available.
Chef now wants to revenge the bombings on his city (see IOPC15I ). He is planning to launch a missile to the Fibonazi's country. For calculating the configrations of the missile, he needs to solve Fibonomial equations. The nth Fibonomial (Sn) of order k is a polynomial in x given by
Where Fj is the jth Fibonacci number (F0 = 0, F1 = 1, and so on). He needs your help in evaluating the polynomial at given n, x and k
- The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
- Each of the next T lines contain 3 space separated integers n, x and k
- For each test case, output a single line containing the value of the polynomial modulo 1000000007.
Should contain all the constraints on the input data that you may have. Format it like:
- 1 ≤ T ≤ 10
- 1 ≤ n, x ≤ 10^18
- 1 ≤ k ≤ 40
Input: 1 10 2 2 Output: 12133
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.