#pragma GCC optimize ("O3") #pragma GCC target ("avx") #include #include #include #include #include #include #include using namespace std; typedef __int128 i128; const int N = 8; const int NN = 3; const int M = 200; const i128 B = i128(1e9) * i128(1e9) * i128(1e9); const long long mod = 1e6 + 3; long long fact[mod]; long long ifact[mod]; long long inv[mod]; struct F { // base 10^20 // a[0] . a[1]a[2] ... a[N-1] i128 a[N]; i128 &operator[](int k) { return a[k]; } }; F operator+(F a, F b) { i128 c = 0; for (int i = N-1; i >= 0; i--) { a[i] += b[i] + c; if (a[i] > B) { a[i] -= B; c = 1; } else { c = 0; } } return a; } bool operator==(F a, F b) { for (int i = 0; i < N - NN; i++) { if (a[i] != b[i]) return false; } return true; } bool operator<(F a, F b) { for (int i = 0; i < N - NN; i++) { if (a[i] != b[i]) return a[i] < b[i]; } return false; } bool operator>(F a, F b) { for (int i = 0; i < N - NN; i++) { if (a[i] != b[i]) return a[i] > b[i]; } return false; } bool operator>=(F a, F b) { for (int i = 0; i < N - NN; i++) { if (a[i] != b[i]) return a[i] > b[i]; } return true; } F half(F a) { i128 c = 0; for (int i = 0; i < N; i++) { a[i] += c * B; c = a[i] % 2; a[i] /= 2; } return a; } F from_int(i128 n) { F a = {}; a[0] = n; return a; } F from_ratio(i128 a, i128 b) { F ret = {}; ret[0] = a; i128 c = 0; for (int i = 0; i < N; i++) { ret[i] += c * B; c = ret[i] % b; ret[i] /= b; } return ret; } void print(i128 a) { if (a == 0) { printf("0"); return; } char buf[100]; int ptr = 0; while (a > 0) { buf[ptr++] = a % 10 + '0'; a /= 10; } for (int i = ptr - 1; i >= 0; i--) { putchar(buf[i]); } } void print_fix(i128 a, int d) { char buf[100]; int ptr = 0; for (int i = 0; i < d; i++) { buf[ptr++] = a % 10 + '0'; a /= 10; } for (int i = ptr - 1; i >= 0; i--) { putchar(buf[i]); } } void show(F a) { print(a[0]); putchar('.'); for (int i = 1; i < 5; i++) { putchar(' '); print_fix(a[i], 27); } printf("\n"); } long long can_take(long long a, F b) { long long ok = 0; long long ng = 2e18; while (ng - ok > 1) { long long mid = (ok + ng) / 2; if (from_ratio(a + mid, mid) >= b) { ok = mid; } else { ng = mid; } } return ok; } long long C(int n, int r) { if (n < r) return 0; return fact[n] * ifact[r] % mod * ifact[n - r] % mod; } long long lucas(long long n, long long r) { if (n == 0 && r == 0) return 1; return C(n % mod, r % mod) * lucas(n / mod, r / mod) % mod; } int main() { fact[0] = 1; fact[1] = 1; ifact[0] = 1; ifact[1] = 1; inv[1] = 1; for (int i = 2; i < mod; i++) { fact[i] = fact[i - 1] * i % mod; inv[i] = inv[mod % i] * (mod - mod / i) % mod; ifact[i] = ifact[i - 1] * inv[i] % mod; } vector cnt(26); for (int i = 0; i < 26; i++) { cin >> cnt[i]; } string s; cin >> s; vector sum(26); for (char c : s) { sum[c - 'a']++; } for (int i = 0; i < 26; i++) { if (sum[i] > cnt[i]) { cout << 0 << endl; return 0; } cnt[i] -= sum[i]; } vector> g(26); int i = 0; while (i < s.size()) { int j = i; while (i < s.size() && s[i] == s[j]) { i++; } g[s[j] - 'a'].push_back(i - j); } long long ans = 1; for (int iii = 0; iii < 26; iii++) { auto x = g[iii]; long long C = cnt[iii]; F ok = from_int(1); F ng = from_int(2e18); if (C == 0) continue; clock_t beg = clock(); map xs; for (int e : x) xs[e]++; for (int ii = 0; ii < M; ii++) { F mid = half(ok + ng); // x[0]/1 (x[0]+1)/2 (x[0]+2)/3 ... // (x + k) / k >= mid i128 t = 0; for (auto kv : xs) { t += can_take(kv.first, mid) * kv.second; } if (t >= C) { ok = mid; } else { ng = mid; } } // fprintf(stderr, "%.4f\n", (double)(clock() - beg) / CLOCKS_PER_SEC); vector take(x.size()); for (int i = 0; i < x.size(); i++) { take[i] = can_take(x[i], ng); C -= take[i]; } for (int i = 0; i < x.size(); i++) { if (C > 0 && can_take(x[i], ok) > can_take(x[i], ng)) { take[i]++; C--; } } #ifdef FOO cout << x.size() << endl; cout << C << endl; #endif for (int i = 0; i < x.size(); i++) { #ifdef FOO cout << i << ' ' << x[i] << ' ' << take[i] << ' ' << lucas(x[i] + take[i], take[i]) << endl; #endif ans *= lucas(x[i] + take[i], take[i]); ans %= mod; } #ifdef FOO cerr << "ok "; show(ok); #endif } cout << ans << endl; }