FIBHARD - Hard Fibonacci
The problem author is not a very nice person. He wants you to calculate the Nth fibonacci number, which is defined as:
Because the author is not very nice, the size of N can be huge, really huge. The exact size of N is in the Constraints section.
Input
The first line contains a single integer T, the number of test cases.
The next T lines contain a single integer N.
Output
For each of the T lines, output the Nth fibonacci number, modulo 998244353.
Example
Input:
5
0
1
1234
345639696828452375
419384601238473729475639183948326177846782649592628790267300203877
Output:
0
1
4936310
213237811
389871463
Constraints
- 0 ≤ N ≤ 1015000000
- 1 ≤ T ≤ 100
Notes
- The size of the file will not exceed 15MB.
- Fast input may be required.
- Fast languages like C / C++ are recommended.
Added by: | dingledooper |
Date: | 2019-10-30 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |