Gunga forgot his computer password again! Darned password manager. He called the campus tech assistants and was able to reset his password. Wahoo!! The first $$$4$$$ digits of his new password are $$$5341$$$ and he noticed that the total of these digits ($$$5+3+4+1=13$$$) is a prime number. His password is $$$n$$$ digits long and each digit is a number from 0 to 9. It didn't take him much time to check all the consecutive 4 digit numbers and add the digits. He was surprised to find that all $$$n-4+1$$$ consecutive quadruplets sum to prime numbers. He gave a name to this type of password: prime-words.
He starts to wonder how many possible $$$n$$$ digit passwords are prime-words. For example, when $$$n=5$$$, $$$53419$$$ is a prime-word since $$$5+3+4+1=13,3+4+1+9=17$$$ are both prime. Each digit can be $$$0-9$$$. Help Gunga find the number of $$$n$$$ digit prime-words (the total of each consecutive 4 digits is a prime number). Since the number can be large, output the answer $$$\pmod{10^9+7}$$$.
The first line contains a single integer $$$n$$$ $$$(1\le n\le 5\times 10^4)$$$ - the number of digits.
A single integer, the number of $$$n$$$ digit prime-words $$$\pmod{10^9+7}$$$.
4
3010
10
3163025