Rest at the sea is wonderful! However, programmer Pasha became awfully
bored of lying on a beach in Turkey; so bored that he decided to count the
quantity of three-digit prime numbers. This turned out to be so
interesting that he then started to study threeprime numbers. Pasha
calls an integer a threeprime number if any three consecutive digits of this integer
form a three-digit prime number. Pasha had already started working
on the theory of the divine origin of such numbers when some vandals
poured water on Pasha and cried some incomprehensible words like
“Sonnenstich!”, “Colpo di sole!”, and “Coup de soleil!”
You are to continue Pasha’s work and find out how often (or rare)
threeprime numbers are.
The input contains an integer n (3 ≤ n ≤ 10000).
Output the quantity of n-digit threeprime numbers calculated
modulo 109 + 9.
Problem Author: Denis Musin
Problem Source: ACM ICPC 2007–2008. NEERC. Eastern Subregion. Yekaterinburg, October 27, 2007