This problem is a programming version of Problem 164 from projecteuler.net
How many numbers (without any leading zero) exist such that no three consecutive digits of have a sum greater than 9?
Print answer modulo .
Input Format
One integer is given on first line representing .
Constraints
Output Format
Print one integer which is the answer modulo
Sample Input 0
3
Sample Output 0
165