CLASSICSEQ - Classic Sequence Sum

Find the value of sum of square of all the first N numbers in Fibonacci series.

Input

First line of every input test file contains T denoting the number of test cases for the file, followed by T numbers N.

Output

For every number N output the result( sum of square of first N Fibonacci numbers) in the below described format.

Value can overflow the standard data type, output the result modulo 1000000007 (109 + 7).

Constraints

1 <= T <= 10000 (104)

1 <= N <= 1000000000000000000 (1018)

Example

Input:
3
1
5
10
Output: Case 1: 1
Case 2: 40
Case 3: 4895

Added by:ad
Date:2018-10-20
Time limit:1s-3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Mostafa M. Mohamed

hide comments
2022-10-09 17:44:26
we know that,

for all the real number of n,
sum(j = 1 to n) f(j^2) = f(n) * f(n + 1)

basis for the introduction:
...........................

we know that f(1)^2 = 1 = f(3) - 1

from(j = 1 to 1) f(j)^2 = f(1)^2 = 1 * 1 = 1
= f(1) * f(2)

from the rules of the induction hypothesis:
...........................................

sum(i = 1 to k) f(i)^2 = f(k) * f(k + 1)

so we need to chow that the
sum(i = 1 to k + 1) f(i)^2 = f(k + 1) * f(k + 2)

induction step:
...............

sum(i = 1 to k + 1) f(i)^2 = sum(i = 1 to k)f(i)^2 + f(k + 1)^2
= f(k) * f(k + 1) + f(k + 1)^2
= f(k + 1) * (f(k) + f(k + 1))
= f(k + 1) * f(k + 2)

so can say that p(k) => p(k + 1)

so all number from 1 to n,
f(n)^2 = f(n) * f(n + 1)

Last edit: 2022-10-10 19:23:01
2022-10-04 11:29:49 Simes
Apparently, the square of Fibonacci numbers from 1 to n is equal to the nth Fibonacci number multiplied by the n+1 th Fibonacci number.

So the problem then becomes being able to calculate the appropriate terms of the Fibonacci sequence, and I think matrix multiplication may be used here.
2022-10-04 06:55:23
Can I get some of the hint to solve this problem?
2018-10-20 19:21:59
Thanks [Lakshman] for suggesting right place.
2018-10-20 18:14:06 [Lakshman]
I don't think this problem is relevant to the classical section. Should be moved to Tutorials

Last edit: 2018-10-20 20:35:37
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.