#28 「 数数字 」

统计

R君十分喜欢计数,他有一天遇到了这样的一个问题:

求这样的n位数个数:数字的各个数字都是奇数,而且1和3必须出现且出现偶数次。

R君陷入了沉思,现在你来帮帮他吧。

因为答案很大,所以只需对$10^9+7$取模就好了。

输入格式

输入包含一行一个整数n。

输出格式

输出共一行一个整数,表示答案。

样例数据

input

5

output

90

数据规模与约定

$n \le 10^{15}$。

时间限制:1s

空间限制:512MB

Author: zrt