FIBEZ - Easy Fibonacci


Fibonacci numbers are well-known in mathematics. But there is a problem. Your friend keeps asking you the nth Fibonacci number. He understands that the number can be very big. So, he asks you to modulo it by 108 + 7 before you give your answer to him.

In this case, the first 5 Fibonacci numbers are 1, 1, 2, 3, 5.

Input

First line contains an integer T (0 < T <= 106) defining the number of test case.

Each of next T lines contains n (0 < n <= 5.105).

Output

For every test case, print an nth Fibonacci number in a line after it has been moduloed by 108 + 7.

Example

Input:
5
1
2
3
4
5 Output: 1
1
2
3
5

hide comments
akshay_289: 2024-11-08 19:37:36

In one word : spoj is trush

shivansh961: 2023-05-19 06:41:12

<snip>
[Simes]: use the forum for code discussions

Last edit: 2023-05-19 07:44:12
deependra_18: 2020-04-16 07:42:06

using matrix exp T*log(n) in My case- TLE
using dp with fast i/o got AC in o(T);

Last edit: 2020-04-18 18:05:39
himanshu_12345: 2017-08-30 18:18:26

use scanf and printf whose code is getting TLE

Robert Lewon: 2017-04-11 10:00:03

Thank you for moving problem to tutorial section.

makeitdonesolo: 2017-04-05 17:07:15

Please move to Tutorial Section.

[Rampage] Blue.Mary: 2017-04-05 07:17:33

This is surely a tutorial problem, please move ASAP.


Added by:Lucas
Date:2017-02-23
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All