D. Primewords Revisit
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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}$$$.

Input

The first line contains a single integer $$$n$$$ $$$(1\le n\le 5\times 10^4)$$$ - the number of digits.

Output

A single integer, the number of $$$n$$$ digit prime-words $$$\pmod{10^9+7}$$$.

Examples
Input
4
Output
3010
Input
10
Output
3163025