我们首先枚举一下有多少个奇数（0-5个）出现在了数中，然后把它们（注意有些奇数数量有多种方式，例如出现1个奇数可能是出现1，3，5，7，或者9，所以计算ans时有些地方乘了5、10）的数量加起来，就是所有可能性的和。
上面的变换，使得计算时，不需要在下面的状态中特殊考虑一个奇数位根本不存在的情况，简化了状态的设置。
任何一个数字都有一个状态(a, b)（a, b均不超过5），表示该数当前有a个奇数位的数量不符合要求，有b个偶数位的数量不符合要求。
在(a, b)状态，并且长度为x位的数的数量，可以从x-1位的值递推出来。绚丽多彩的数，就是在(0, 0)状态的数。
因为题目要求位数不超过n，而不要求位数正好为n，我们再引入一个X状态（代码中表示为36状态)，意思是数字还没有开始。
使用矩阵乘法优化一下这个递推，就可以做出来了。

#include <cstdio>
#include <algorithm>

#define ll long long
#define encode(badodd, badeven) (6 * (badodd) + (badeven))

using namespace std;

ll n, p;

ll matrix_a[37][37];

ll fastpow[61][37][37];

ll matrix_b[37][37];
ll matrix_temp[37][37];

void matmul(ll ans[37][37], ll a[37][37], ll b[37][37])
{
    for (int i = 0; i <= 36; i++) {
        for (int j = 0; j <= 36; j++) {
            ans[i][j] = 0;
            for (int k = 0; k <= 36; k++) {
                ans[i][j] += a[i][k] * b[k][j];
                ans[i][j] %= p;
            }
        }
    }
}

void matcopy(ll to[37][37], ll from[37][37])
{
    for (int i = 0; i <= 36; i++) {
        for (int j = 0; j <= 36; j++) {
            to[i][j] = from[i][j];
        }
    }
}

ll calc(int oddcnt)
{
    for (int i = 0; i <= 36; i++) {
        for (int j = 0; j <= 36; j++) {
            matrix_a[i][j] = 0;
        }
    }
    matrix_a[36][36] = 1;
    for (int i = 0; i <= oddcnt; i++) {
        for (int j = 0; j <= 5; j++) {
            matrix_a[encode(i, j)][encode(i - 1, j)] = i;
            matrix_a[encode(i, j)][encode(i + 1, j)] = oddcnt - i;
            matrix_a[encode(i, j)][encode(i, j - 1)] = j;
            matrix_a[encode(i, j)][encode(i, j + 1)] = 5 - j;
        }
    }
    matrix_a[36][encode(oddcnt - 1, 0)] = oddcnt;
    matrix_a[36][encode(oddcnt, 1)] = 4;
    
    matcopy(fastpow[0], matrix_a);
    for (int i = 1; i <= 60; i++) {
        matmul(fastpow[i], fastpow[i - 1], fastpow[i - 1]);
    }
    for (int i = 0; i <= 36; i++) {
        for (int j = 0; j <= 36; j++) {
            if (i == j) {
                matrix_b[i][j] = 1;
            } else {
                matrix_b[i][j] = 0;
            }
        }
    }
    ll cur = 1;
    for (int i = 0; i <= 60; i++) {
        if (n & cur) {
            matmul(matrix_temp, matrix_b, fastpow[i]);
            matcopy(matrix_b, matrix_temp);
        }
        cur *= 2;
    }
    return matrix_b[36][0];
}

int main()
{
    scanf("%lld%lld", &n, &p);
    /*int nval, pval;
    scanf("%d%d", &nval, &pval);
    n = nval;
    p = pval;*/
    ll ans = (calc(5) + 5 * calc(4) + 10 * calc(3)
              + 10 * calc(2) + 5 * calc(1) + calc(0)) % p;
    printf("%lld", ans);
    return 0;
}