#include <bits/stdc++.h> #define int long long #define pii pair<int,int> #define mkp make_pair #define push_back emplace_back const int mod = 998244353; using namespace std; inline int read() { int fl = 1, x; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') fl = -1; c = getchar(); } while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar(); return fl * x; } int n, w, m2[200005], f[200005][3], f2[200005][3]; char s[200005]; inline int ksm(int x, int y) { int res = 1; while (y) { if (y & 1) res = res * x % mod; x = x * x % mod, y >>= 1; } return res; } signed main() { //freopen("string.in", "r", stdin); //freopen("string.out", "w", stdout); n = read(), w = read(); // printf("%lld %lld\n", n, w); if (n >= 1e9) { //mt19937_64 rng(clock() + time(0)); //printf("%lld", rng() % 998244353); return 0; } scanf("%s", s + 1); int len = strlen(s + 1); m2[0] = 1; for (int i = 1; i <= len + 1; i++) { m2[i] = (m2[i - 1] << 1) % mod; } if (w == 2 || w == 5) { int c = 0; if (w == 2) { for (int i = 1; i <= len; i++) { if (s[i] == '2' || s[i] == '4' || s[i] == '6' || s[i] == '8') c = (c + m2[i - 1]) % mod; } } else { for (int i = 1; i <= len; i++) { if (s[i] == '5') c = (c + m2[i - 1]) % mod; } } int res = 1, l2 = m2[len]; for (int i = 1; i <= n; i++) { res = (res + c) % mod; c = (c * l2) % mod; } printf("%lld\n", res); } else { f[0][0] = 1; for (int i = 1; i <= len; i++) { if ((s[i] - '0') % 3 == 0) { f[i][0] = f[i - 1][0] * 2 % mod; f[i][1] = f[i - 1][1] * 2 % mod; f[i][2] = f[i - 1][2] * 2 % mod; } else if ((s[i] - '0') % 3 == 1) { f[i][0] = (f[i - 1][0] + f[i - 1][2]) % mod; f[i][1] = (f[i - 1][1] + f[i - 1][0]) % mod; f[i][2] = (f[i - 1][2] + f[i - 1][1]) % mod; } else { f[i][0] = (f[i - 1][0] + f[i - 1][1]) % mod; f[i][1] = (f[i - 1][1] + f[i - 1][2]) % mod; f[i][2] = (f[i - 1][2] + f[i - 1][0]) % mod; } } f2[0][0] = 1; for (int i = 1; i <= n; i++) { for (int j = 0; j < 3; j++) { f2[i][j] = (f2[i - 1][0] * f[len][j] % mod + f2[i - 1][1] * f[len][(j + 2) % 3]) % mod + (f2[i - 1][2] * f[len][(j + 1) % 3]) % mod; } } printf("%lld\n", f2[n][0]); } //fclose(stdout); return 0; }