说明

学校放假啦！徐老师获得了一个长达 $n$ 天的假期

但是众所周知，假期必然伴随着作业

徐老师作为一个努力学习的人，自然是要提前规划好每天的学习任务

现在徐老师打算每天都用一个努力值 $(0 \sim 9)$ 来表示自己今天的学习勤奋程度

现在徐老师突然有了个想法，他想知道有多少种不同的学习方案，可以保证相邻两天的努力程度合在一起可以组成一个质数

比如相邻的 $3$ 天努力度分别为 `1 3 1`,那么第 $1$ 天和第 $2$ 天组成的数字 $13$ 是质数，第 $2$ 天和第 $3$ 天组成的数字 $31$ 是质数，则这是一组徐老师想要的学习方案

当然，作为一个努力学习的人，徐老师不会把第一天的努力度设为 $0$

输入格式

输入为 $1$ 个整数 $n$ 表示假期天数。

对于 $10\%$ 的测试数据，$n == 2$
对于 $30\%$ 的测试数据，$2 \leq n \leq 8$
对于 $60\%$ 的测试数据，$2 \leq n \leq 11$
对于 $100\%$ 的测试数据，$2 \leq n \leq 1000$

输出格式

输出为 $1$ 个整数，为方案数，结果对 $10007$ 取模。

样例

5

372