### 问题描述 数字王国要举行一次阅兵仪式，现在要从所有数字种遴选出可以参加阅兵的数字。以下是选拔标准： - 数字必须是整数。 - 数字中相邻两位数字之差不超过 $2$。 - 数字一共有 $k$ 位。 必须全部满足以上要求的数字才能参加阅兵。数字国王现在请你帮忙求出，共有多少数字可以参加阅兵。 ### 输入格式 输入包含一个整数 $k$，含义见上文。 ### 输出格式 输出一个整数，表示可以参加阅兵的数字个数。因为答案较大，所以输出对 $10^9+7$ 取模后的结果。 ### 样例输入 ``` 4 ``` ### 样例输出 ``` 867 ``` ### 评测数据规模 对于所有评测数据，$1\leq{k}\leq{10^{18 }}$。