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 fib, number) 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

hide comments
atu1_rana: 2018-10-20 19:21:59

Thanks [Lakshman] for suggesting right place.

[Lakshman]: 2018-10-20 18:14:06

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

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