湘潭赛Easy wuxing（递推+矩阵快速幂or DP）

十分感谢老师的思路！

题目描述
“五行”是中国传统哲学思想，它认为认为大自然的现象由“木、火、土、金、水”这五种气的变化所总括， 不但影响到人的命运，同时也使宇宙万物循环不已。 五行具有相生相克的性质，规律如下：

五行相克：金克木，木克土，土克水，水克火，火克金。
五行相生：金生水，水生木，木生火，火生土，土生金。
五行任一行与其他五行的关系为：同我、生我、我生、克我、我克。

给你一个1*n的格子，将五行填上去，每格填一个，要求相邻格以及首尾格不能是同我和相克的关系， 请问一共有多少种不同的方案？

输入
多组样例，每组一个整数n(0≤n≤106)，如果n为0，表示输入结束，这个样例不需要处理。
输出
每行输出一个样例的结果，因为数值可能非常大，请将结果对109+7取模。
样例输入
1
2
0
样例输出
5
10

本题可以使用递推+矩阵快速幂求解，也可以通过使用DP解决。但仅仅使用递推，会导致TLE时间超限。只能够靠矩阵快速幂节约时间。