题目描述

我们称一个数字字符串是好数字， 当它满足(下标从0开始)偶数下标处的数字为偶数且奇数下标处的数字为质数。 比方说，“2582”是好数字，因为偶数下标处的数字(2和8)是偶数且奇数下标处的数字（5和2）为质数。 但“3245”不是好数字，因为3在偶数下标处但不是偶数。 给你一个整数n,请你计算长度为n且为好数字的数字字符串总数。由于答案可能会很大，输出结果对$10^9+7$取余。

一个数字字符串是每一位都由0~9组成的字符串，且可能包含前导0（例如052也是一种合法方案）。

输入格式

一个整数n表示数字字符串的长度（$1<=n<=10^{18}$）。

输出格式

好数字的个数，输出结果对$10^9+7$取余。

1

5

4

400

数据规模与约定

样例1解释： 长度为1的好数字包括“0”，“2”，“4”，“6”，“8”。