10160번: 암호

https://www.acmicpc.net/problem/10160

#include<stdio.h>
#define MaxN
long long int n, k, ans;
long long int dy[1000010][10], f[10][10];
int main()
{
    int i, j, l;
 
    scanf("%lld%lld", &n, &k);
    f[1][1] = k - 1; f[1][2] = 1;
    f[2][1] = k - 2; f[2][2] = f[2][3] = 1;
    f[3][1] = k - 2; f[3][4] = f[3][6] = 1;
    f[4][1] = k - 2; f[4][2] = f[4][5] = 1;
    f[5][1] = k - 2; f[5][2] = 1;
    f[6][1] = k - 2; f[6][2] = f[6][7] = 1;
    f[7][1] = k - 2; f[7][6] = 1;
    dy[1][1] = k - 1;
    dy[1][2] = 1;
    for (i = 2; i <= n; i++)
    {
        for (j = 1; j <= 7; j++)
        {
            for (l = 1; l <= 7; l++)
            {
                dy[i][j] = (dy[i][j] + dy[i - 1][l] * f[l][j]) % 1000000009;
            }
        }
    }
    for (i = 1; i <= 7; i++)
    {
        ans = (ans + dy[n][i]) % 1000000009;
    }
    printf("%lld", ans);
    return 0;
}