Background

蛟川书院的一道练习题QAQ

Description

如果一个数的所有连续三位数字都是大于100的素数，则该数称为三素数数。比如113797是一个6位的三素数数。

Input

一个整数n（3 ≤ n ≤ 10000），表示三素数数的位数。

Output

一个整数，表示n位三素数的个数m，要求输出m除以10^9 + 9的余数。

Samples

4

204

Limitation

1s, 1024KiB for each test case.