SFN - Square Free Number
A Square free number is a number whose sum of every adjacent two digits is not a perfect square and doesn't contain digit 0. For example, 123 is a square free number cause sum of first two adjacent digits 1 + 2 = 3 is not a perfect square and sum of last two adjacent digits 2 + 3 = 5 is not a perfect square.
You are given an integer n. You have to calculate the number of n-digit square free number.
As the result can be very big, output the result modulo 1000000007 (1e9 + 7).
Input
First line of the input contains a number T, the number of test cases.
Each of the next T lines will contain an integer n.
Output
Output the number of square free numbers of length n.
Constraints
T <= 1000.
1 <= n <= 1018.
Example
Input: 3 1 2 3 Output: 6 67 501
Note: By definition 1, 4, 9 is not square free number.
hide comments
rgoewedky:
2020-08-30 06:28:22
Digit DP Last edit: 2021-03-13 04:24:19 |
|
abhineelnandi:
2020-06-19 09:03:41
O(T * log(N) [* 10^3]) solution via matrix exponentiation.
|
|
mehmetin:
2019-05-09 18:34:26
n <= 2147483647 for all cases. |
Added by: | Prodip |
Date: | 2019-05-02 |
Time limit: | 2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |