该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

时间限制：1 Sec 内存限制：256 MB 输入文件：crotate.in 输出文件：crotate.out

小 B 看到数字 $90106$ 时，产生了一个想法：

> “这个数字以中间位置为轴旋转 $180°$ 后，是不是还是 $90106$ 呢？”

请你求出满足以下条件的 $N$ 位数字的个数（结果对 $10^9+7$ 取模）：

1.  以数字的中间位置为轴旋转 $180$ 度后，得到的数字与原数字完全相同；

2.  首位不能为 $0$。

旋转规则说明：

数字的 180° 旋转遵循以下规则：

- 数字 $1$、$8$、$0$ 旋转 180° 后，形状保持不变；

- 数字 $6$ 旋转 180° 后变为 $9$，数字 $9$ 旋转 180° 后变为 $6$；

- 其他数字（$2$、$3$、$4$、$5$、$7$）旋转 180° 后，无法与任何数字的形状重合。

> 补充说明：

> 虽然旋转 180° 后数字 $1$ 的形状看起来可能和原形状略有不同，但本题中将其视为与原数字相同。

输入格式

一个整数 $N$，表示数字的位数。

输出格式

输出一行一个整数，表示满足条件的 $N$ 位数字的个数，结果对 $10^9+7$ 取模。

样例

样例 1

2

4

样例说明：

满足条件的 $2$ 位数有 $4$ 个：$11$、$69$、$88$、$96$。

样例 2

3

12

样例说明：

满足条件的 $3$ 位数有 $12$ 个：$101$、$111$、$181$、$609$、$619$、$689$、$808$、$818$、$888$、$906$、$916$、$986$。

样例 3

57

237171741

样例 4

864

926092950

数据范围

对于 12% 的数据，$N \le 200$。

对于 28% 的数据，$N \le 100000$。

对于 100% 的数据，$1 \le N \le 10^{18}$。