### 问题描述 小蓝开了一家数字拼装商店。他的商店运营模式如下： 顾客会告诉小蓝他想要的数字位数 $n$，而后小蓝要选择 $n$ 个数字将这个数字拼装出来。注意，这个拼装出的数字的所有连续三位数字都必须是大于 $100$ 的素数。例如，$113797$ 是一个 $6$ 位的符合要求的拼装数字。 小蓝有一天突发奇想，他想知道 $n$ 位的符合要求的拼装数字一共有多少个。因为答案可能过大，所以他希望输出对 $10^9+9$ 取余的结果。 ### 输入格式 输入包含一个整数 $n$，含义见上文。 ### 输出格式 输出一个整数，表示模 $10^9 +9$ 意义下 $n$ 位的符合要求的拼装数字的个数。 ### 样例输入 ``` 4 ``` ### 样例输出 ``` 204 ``` ### 评测数据规模 对于所有评测数据，$3\leq{n}\leq{10^4}$。