#include <bits/stdc++.h> #include <atcoder/modint> using namespace std; using namespace atcoder; using ll = long long; using mint = modint1000000007; int main(){ cin.tie(nullptr); ios_base::sync_with_stdio(false); /* 部分列DP dp(i) = i文字目まででの部分文字列の種類数 c=a,...,zのi以降の最小のインデックスp_cに dp(p_c) += dp(i) dp(i) = i文字目の塊まででの部分文字列の種類数 異なる文字(S_i != S_j) -> jのどこで止めるか? dp(j) += dp(i) * A_j 同じ文字列(S_i == S_j) -> 重複を避けるために、A_iの末尾からの遷移しか許可しない。 iiooii A_1までi, ii (2) A_3までi+i, i+ii, ii+i, ii+ii (3) dp(i, j) = i文字目の塊までで、i文字目の塊を全て使った(j=1)か使ってない(j=0)ときの部分文字列の数 */ int N; cin >> N; vector<int> A(N+1); for (int i=1; i<=N; i++) cin >> A[i]; string S; cin >> S; S = '$' + S; char c; vector<vector<int>> v(26); for (int i=1; i<=N; i++){ c = S[i]; v[c-'a'].push_back(i); } mint ans=0; vector dp(N+1, vector<mint>(2)); dp[0][0] = 1; for (int i=0; i<=N; i++){ c = S[i]; for (int j=0; j<26; j++){ auto it = lower_bound(v[j].begin(), v[j].end(), i+1); if (it != v[j].end()){ if (c-'a' == j){ dp[*it][1] += dp[i][1]; dp[*it][0] += dp[i][1] * (A[*it]-1); } else{ dp[*it][1] += dp[i][1] + dp[i][0]; dp[*it][0] += (dp[i][1] + dp[i][0]) * (A[*it]-1); } } } } for (int i=1; i<=N; i++) ans += dp[i][0] + dp[i][1]; cout << ans.val() << endl; return 0; }