#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i)) #define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i)) #if defined(_MSC_VER) || __cplusplus > 199711L #define aut(r,v) auto r = (v) #else #define aut(r,v) __typeof(v) r = (v) #endif #define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it) #define all(o) (o).begin(), (o).end() #define pb(x) push_back(x) #define mp(x,y) make_pair((x),(y)) #define mset(m,v) memset(m,v,sizeof(m)) #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3fLL using namespace std; typedef vector vi; typedef pair pii; typedef vector > vpii; typedef long long ll; template inline void amin(T &x, U y) { if(y < x) x = y; } template inline void amax(T &x, U y) { if(x < y) x = y; } struct SaturationInt { typedef unsigned long long T; typedef double Float; static T Max; T x; static inline T sat(T x) { return x > Max ? Max : x; } SaturationInt(): x(0) { } SaturationInt(T x_): x(sat(x_)) { } T get() const { return x; } SaturationInt operator+(const SaturationInt &that) const { return SaturationInt(x + that.x); } SaturationInt operator*(const SaturationInt &that) const { return SaturationInt((Float)x * that.x > Max ? Max : x * that.x); } SaturationInt &operator+=(const SaturationInt &that) { return *this = *this + that; } SaturationInt &operator*=(const SaturationInt &that) { return *this = *this * that; } SaturationInt operator^(long long k) const { T r = 1, a = x; while(k) { if(k & 1) r *= a; if(k >>= 1) { if((Float)a * a * r > Max) return SaturationInt(Max); a *= a; } } return SaturationInt(r); } bool operator<(const SaturationInt &that) const { return x < that.x; } }; SaturationInt::T SaturationInt::Max = (1ULL << 63) - 1; typedef SaturationInt sint; const int NCR_TABLE_N = 2000; sint nCrTable[NCR_TABLE_N+1][NCR_TABLE_N+1]; sint nCr(long long x, long long y) { if(nCrTable[0][0].x == 0) { for(int i = 0; i <= NCR_TABLE_N; i ++) { nCrTable[i][0] = 1; for(int j = 1; j <= i; j ++) nCrTable[i][j] = nCrTable[i-1][j-1] + nCrTable[i-1][j]; } } if(x < y) return sint(); if(y > x / 2) y = x - y; if(y == 0) return sint(1); if(y == 1) return sint(x); if(y == 2) { long long a[2] = {x, x - 1}; a[x % 2] /= 2; return sint(a[0]) * sint(a[1]); } if(y == 3) { long long a[3] = {x, x - 1, x - 2}; a[x % 2] /= 2; a[x % 3] /= 3; return sint(a[0]) * sint(a[1]) * sint(a[2]); } if(y == 4) { long long a[4] = {x, x - 1, x - 2, x - 3}; a[(x % 2 == x % 4 ? 2 : 0) + x % 2] /= 2; a[x % 3] /= 3; a[x % 4] /= 4; return sint(a[0]) * sint(a[1]) * sint(a[2]) * sint(a[3]); } if(y == 5) { long long a[5] = {x, x - 1, x - 2, x - 3, x - 4}; a[(x % 2 == x % 4 ? 2 : 0) + x % 2] /= 2; a[x % 3] /= 3; a[x % 4] /= 4; a[x % 5] /= 5; return sint(a[0]) * sint(a[1]) * sint(a[2]) * sint(a[3]) * sint(a[4]); } if(y == 6) { long long a[6] = {x, x - 1, x - 2, x - 3, x - 4, x - 5}; a[x % 5] /= 5; rep(k, 6) { if(a[k] % 2 == 0) a[k] /= 2; break; } rep(k, 6) { if(a[k] % 2 == 0) a[k] /= 2; break; } rep(k, 6) { if(a[k] % 2 == 0) a[k] /= 2; break; } rep(k, 6) { if(a[k] % 2 == 0) a[k] /= 2; break; } rep(k, 6) { if(a[k] % 3 == 0) a[k] /= 3; break; } rep(k, 6) { if(a[k] % 3 == 0) a[k] /= 3; break; } return sint(a[0]) * sint(a[1]) * sint(a[2]) * sint(a[3]) * sint(a[4]) * sint(a[5]); } if(x > NCR_TABLE_N) { return sint(sint::Max); } else { return nCrTable[(int)x][(int)y]; } } template vector > runLength(const T a[], int n) { vector > r; if(n <= 0) return r; int cnt = 0; for(int i = 0; i <= n; i ++) { if(i == n || (i != 0 && a[i] != a[i-1])) { r.push_back(make_pair(a[i-1], cnt)); cnt = 0; } cnt ++; } return r; } sint solve(long long x, int y, int n) { sint ans = 1; ans *= nCr(y + x / n, y) ^ (n - x % n); ans *= nCr(y + x / n + 1, y) ^ (x % n); return ans; } int main() { const int Alphas = 26; char *T = new char[1000001]; vector S(Alphas); for(int i = 0; i < Alphas; ++ i) scanf("%lld", &S[i]); scanf("%s", T); auto runs = runLength(T, strlen(T)); vector lengths(Alphas); for(auto p : runs) { int a = p.first - 'a'; S[a] -= p.second; lengths[a].push_back(p.second); } sint ans = 1; rep(a, Alphas) { long long x = S[a]; if(x < 0) { ans *= 0; continue; } vi &v = lengths[a]; sort(all(v), greater()); if(v.empty()) continue; auto w = runLength(&v[0], v.size()); if(w.size() == 1) { ans *= solve(x, w[0].first, w[0].second); continue; } vector sum(w.size() + 1, 0); for(int i = (int)w.size() - 1; i >= 0; -- i) sum[i] = sum[i+1] + w[i].first * w[i].second; map dp, ndp; dp[x] = 1; rep(k, w.size()) { int y = w[k].first, n = w[k].second; double ratio = y * n * 1. / sum[k]; ndp.clear(); for(auto p : dp) { long long remx = p.first; sint t = p.second; long long a = (long long)(remx * ratio); for(long long b = max(0LL, a - 2); b <= min(remx, a + 2); ++ b) { amax(ndp[remx - b], t * solve(b, y, n)); } } sint maxi; dp.clear(); for(auto it = ndp.rbegin(); it != ndp.rend(); ++ it) { if(maxi < it->second) { maxi = it->second; dp.insert(*it); } } if(maxi.get() >= 1ULL << 62) break; } sint maxi; for(auto p : dp) amax(maxi, p.second); ans *= maxi; } if(ans.get() >= 1ULL << 62) { puts("hel"); } else { cout << ans.get() << endl; } return 0; }