Let F(n) be the nth member of the Fibonacci sequence:
F(0) = 0, F(1) = 1, F(n) = F(n - 1) + F(n - 2) (n > 1)
Consider the following Fibonacci polynomial:
A(n, x) = x · F(1) + x2 · F(2) + x3 · F(3) + ... + xn · F(n)
= Σ(xn · F(n)) for n in range [1..n].
For example, A(7, x) = x1 + x2 + 2x3 + 3x4 + 5x5 + 8x6 + 13x7
So:
A (7, 1) = 33
A (7, 0) = 0
A (7, 10) = 138532110
Find A(n, x) for the given n, x.
Because the value may be very large, give your answer MODULO 108
[input] string N
1 ≤ N ≤ 252.
[input] integer X
0 ≤ X ≤ 100.
[output] integer
A(N, X) modulo 108.
F(0) = 0, F(1) = 1, F(n) = F(n - 1) + F(n - 2) (n > 1)
Consider the following Fibonacci polynomial:
A(n, x) = x · F(1) + x2 · F(2) + x3 · F(3) + ... + xn · F(n)
= Σ(xn · F(n)) for n in range [1..n].
For example, A(7, x) = x1 + x2 + 2x3 + 3x4 + 5x5 + 8x6 + 13x7
So:
A (7, 1) = 33
A (7, 0) = 0
A (7, 10) = 138532110
Find A(n, x) for the given n, x.
Because the value may be very large, give your answer MODULO 108
[input] string N
1 ≤ N ≤ 252.
[input] integer X
0 ≤ X ≤ 100.
[output] integer
A(N, X) modulo 108.
