All submissions for this problem are available.
Chef Neel is very superstitious. He considers only those number lucky for him in which the difference between two consecutive digits is exactly one. Chef is curious to know how many lucky numbers containing exactly N digits exist .Therefore Chef gives his apprentice a task i.e. Given an integer N, find the number of all N digits lucky numbers.
The first line of input contains a single integer T, the number of test cases.
For each test case there is a single integer N, the number of digits
For each test case output in a new line the count of all distinct N digit lucky numbers modulo 1000000007.
- 1 ≤ T ≤ 100
- 1 ≤ N ≤ 10^5
- Sum of N over all the test cases in an input file does not exceed 10^5.
Input: 2 1 2 Output: 10 17
Example case 1.
For N=1, crazy numbers are 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 .
For N=2, crazy numbers are 10 , 12 , 21 , 23 , 32 , 34 , 43 , 45 , 54 , 56 , 65 , 67 , 76 , 78 , 87 , 89 , 98.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.