时间限制：1秒　　内存限制：256M

---

【题目描述】

　　在所有的n位正整数中，有多少个数中有偶数个数字3（说明，0是偶数）？

【输入格式】

　　一个正整数 \(n\)。

【输出格式】

　　输出含有偶数个数字3的整数个数，由于方案个数会很多，所以输出它 \(mod\ 10……9+7\) 后的结果。

【输入输出样例】

　Input

2

　Output

73

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤n≤10^{18}\)

【来源】

　　Mr.he**