• Source 
    1. #include <iostream>
    2. #include <cstdio>
    3. #include <vector>
    4. using namespace std;
    5. const long long MOD=1000000007;
    6. vector<int> graph[12];
    7. unsigned long long a[100001][11];
    8. int main()
    9. {
    10. 	int t,k,i,j,n,m,b,c,d,e,f;
    11. 	graph[0].push_back(7);
    12.  
    13. 	graph[1].push_back(2);
    14. 	graph[1].push_back(4);
    15.  
    16. 	graph[2].push_back(1);
    17. 	graph[2].push_back(3);
    18. 	graph[2].push_back(5);
    19.  
    20. 	graph[3].push_back(2);
    21. 	graph[3].push_back(6);
    22.  
    23. 	graph[4].push_back(1);
    24. 	graph[4].push_back(5);
    25. 	graph[4].push_back(7);
    26.  
    27. 	graph[5].push_back(2);
    28. 	graph[5].push_back(4);
    29. 	graph[5].push_back(6);
    30. 	graph[5].push_back(8);
    31.  
    32. 	graph[6].push_back(3);
    33. 	graph[6].push_back(5);
    34. 	graph[6].push_back(9);
    35.  
    36. 	graph[7].push_back(4);
    37. 	graph[7].push_back(8);
    38. 	graph[7].push_back(0);
    39.  
    40. 	graph[8].push_back(7);
    41. 	graph[8].push_back(5);
    42. 	graph[8].push_back(9);
    43.  
    44. 	graph[9].push_back(6);
    45. 	graph[9].push_back(8);
    46. 	for(i=0;i<=9;i++)
    47. 		a[1][i]=1;
    48. 	a[1][10]=10;
    49. 	for(i=2;i<=100000;i++)
    50. 	{
    51. 		for(j=0;j<=9;j++)
    52. 		{
    53. 			for(k=0;k<graph[j].size();k++)
    54. 			{
    55. 				a[i][graph[j][k]]+=a[i-1][j];
    56. 			}
    57. 		}
    58. 		for(j=0;j<=9;j++)
    59. 			a[i][j]=a[i][j]%MOD;
    60. 		for(j=0;j<=9;j++)
    61. 			a[i][10]=a[i][10]+a[i][j];
    62. 		a[i][10]=a[i][10]%MOD;
    63. 	}
    64. 	scanf("%d",&t);
    65. 	for(k=1;k<=t;k++)
    66. 	{
    67. 		scanf("%d",&n);
    68. 		printf("%d\n",a[n][10]);
    69. 	}	
    70. 	return 0;
    71. }
    72.  
    73.