Every lock sequence in hogwarts is a sequence of length N and contains digits from 0 - 9 . Now there is a constraint that each lock sequence will not contain two adjacent numbers such that they sum up to a prime number.
For example 9994 is an invalid sequence of lock because 9+4 = 13 but 13 is a prime number. 9993 is a valid sequence of lock beacuse there are no two adjacent numbers such that theys sum up to a prime number.
So for the given length N you have to count total possible lock sequences modulo 10^9+7
First line contains a number N as input
Output total locks possible as per the given constraints
1≤ N ≤ 105
There are 63 locks possible . 00 is also a valid lock sequence.