/* -*- coding: utf-8 -*- * * 2964.cc: No.2964 Obstruction Bingo - yukicoder */ #include #include using namespace std; /* constant */ const int MAX_L = 50; const int MAX_K = 500; const int MOD = 998244353; enum { EQ = 0, A = 1, B = 2 }; /* typedef */ template struct MI { int v; MI(): v() {} MI(int _v): v(_v % MOD) { if (v < 0) v += MOD; } MI(long long _v): v(_v % MOD) { if (v < 0) v += MOD; } explicit operator int() const { return v; } MI operator+(const MI m) const { return MI(v + m.v); } MI operator-(const MI m) const { return MI(v + MOD - m.v); } MI operator*(const MI m) const { return MI((long long)v * m.v); } MI &operator+=(const MI m) { return (*this = *this + m); } MI &operator-=(const MI m) { return (*this = *this - m); } MI &operator*=(const MI m) { return (*this = *this * m); } bool operator==(const MI m) const { return v == m.v; } bool operator!=(const MI m) const { return v != m.v; } MI pow(int n) const { // a^n % MOD MI pm = 1, a = *this; while (n > 0) { if (n & 1) pm *= a; a *= a; n >>= 1; } return pm; } MI inv() const { return pow(MOD - 2); } MI operator/(const MI m) const { return *this * m.inv(); } MI &operator/=(const MI m) { return (*this = *this / m); } }; using mi = MI; /* global variables */ char s[MAX_L + 4], t[MAX_L + 4]; int as[26]; mi ps[26], dp[2][MAX_L][MAX_L][3]; /* subroutines */ /* main */ int main() { int l, k; scanf("%d%d%s%s", &l, &k, s, t); for (int i = 0; i < 26; i++) scanf("%d", as + i); int sum = 0; for (int i = 0; i < 26; i++) sum += as[i]; mi invsum = mi(sum).inv(); for (int i = 0; i < 26; i++) ps[i] = invsum * as[i]; dp[0][0][0][EQ] = 1; int cur = 0, nxt = 1; mi asum = 0, bsum = 0; for (int i = 0; i < k; i++) { for (int a = 0; a < l; a++) for (int b = 0; b < l; b++) fill(dp[nxt][a][b], dp[nxt][a][b] + 3, 0); for (int a = 0; a < l; a++) { int a1 = (a + 1) % l, sa = s[a] - 'a'; for (int b = 0; b < l; b++) { int b1 = (b + 1) % l, tb = t[b] - 'a'; if ((int)dp[cur][a][b][EQ]) { // a == b if (sa == tb) { mi p = ps[sa], q = mi(1) - p; dp[nxt][a1][b1][EQ] += dp[cur][a][b][EQ] * p; dp[nxt][a][b][EQ] += dp[cur][a][b][EQ] * q; } else { mi pa = ps[sa], pb = ps[tb], q = mi(1) - (pa + pb); dp[nxt][a1][b][A] += dp[cur][a][b][EQ] * pa; dp[nxt][a][b1][B] += dp[cur][a][b][EQ] * pb; dp[nxt][a][b][EQ] += dp[cur][a][b][EQ] * q; } } if ((int)dp[cur][a][b][A]) { // a != b if (sa == tb) { mi p = ps[sa], q = mi(1) - p; dp[nxt][a1][b1][A] += dp[cur][a][b][A] * p; dp[nxt][a][b][A] += dp[cur][a][b][A] * q; } else { mi pa = ps[sa], pb = ps[tb], q = mi(1) - (pa + pb); if (a1 == b) asum += dp[cur][a][b][A] * pa; else dp[nxt][a1][b][A] += dp[cur][a][b][A] * pa; if (a == b1) dp[nxt][a][b1][EQ] += dp[cur][a][b][A] * pb; else dp[nxt][a][b1][A] += dp[cur][a][b][A] * pb; dp[nxt][a][b][A] += dp[cur][a][b][A] * q; } } if ((int)dp[cur][a][b][B]) { // a != b if (sa == tb) { mi p = ps[sa], q = mi(1) - p; dp[nxt][a1][b1][B] += dp[cur][a][b][B] * p; dp[nxt][a][b][B] += dp[cur][a][b][B] * q; } else { mi pa = ps[sa], pb = ps[tb], q = mi(1) - (pa + pb); if (a1 == b) dp[nxt][a1][b][EQ] += dp[cur][a][b][B] * pa; else dp[nxt][a1][b][B] += dp[cur][a][b][B] * pa; if (a == b1) bsum += dp[cur][a][b][B] * pb; else dp[nxt][a][b1][B] += dp[cur][a][b][B] * pb; dp[nxt][a][b][B] += dp[cur][a][b][B] * q; } } } } swap(cur, nxt); } printf("%d %d\n", (int)asum, (int)bsum); return 0; }