#include using namespace std; #if __has_include() #include using mint = atcoder::modint1000000007; istream& operator>>(istream& is, mint& a) { int t; is >> t; a = t; return is; } ostream& operator<<(ostream& os, mint a) { return os << a.val(); } #endif #ifdef DEBUG #define _GLIBCXX_DEBUG #else #pragma GCC target("avx2") #pragma GCC optimize("Ofast,unroll-loops") #define cerr if (false) cerr #undef assert #define assert(...) void(0) #undef endl #define endl '\n' #endif #define overload3(a, b, c, name, ...) name #define rep1(n) for (int i = 0; i < n; i++) #define rep2(i, n) for (int i = 0; i < n; i++) #define rep3(i, a, b) for (int i = a; i < b; i++) #define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__) #define per1(n) for (int i = n - 1; i >= 0; i--) #define per2(i, n) for (int i = n - 1; i >= 0; i--) #define per3(i, a, b) for (int i = b - 1; i >= (a); i--) #define per(...) overload3(__VA_ARGS__, per3, per2, per1)(__VA_ARGS__) #define ALL(a) a.begin(), a.end() #define vec vector #undef long #define long long long template ostream& operator<<(ostream& os, vector a) { const int n = a.size(); rep(i, n) os << a[i] << " \n"[i + 1 == n]; return os; } template ostream& operator<<(ostream& os, array a) { rep(i, n) os << a[i] << " \n"[i + 1 == n]; return os; } template istream& operator>>(istream& is, vector& a) { for (T& i : a) is >> i; return is; } template bool chmin(T& x, T y) { if (x > y) { x = y; return true; } return false; } template bool chmax(T& x, T y) { if (x < y) { x = y; return true; } return false; } template void operator++(vector& a) { for (T& i : a) ++i; } template void operator--(vector& a) { for (T& i : a) --i; } template void operator++(vector& a, int) { for (T& i : a) i++; } template void operator--(vector& a, int) { for (T& i : a) i--; } void solve() { int n; cin >> n; vec a(n); cin >> a; string s; cin >> s; vec d(n + 1); atcoder::fenwick_tree fw(n + 1); d[0] = 1; fw.add(0, 1); array pre = {}; rep(i, n) { const int c = s[i] - 'a'; mint val = d[pre[c]] + fw.sum(pre[c] + 1, i + 1); d[i + 1] = val; fw.add(i + 1, val * a[i]); pre[c] = i + 1; } cout << fw.sum(1, n + 1) << endl; } int main() { srand((unsigned)time(NULL)); cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(40); int t = 1; // cin >> t; while (t--) solve(); return 0; }