Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef unsigned long long ull;
- #define all(x) x.begin(), x.end()
- #define rall(x) x.rbegin(), x.rend()
- #define endl '\n'
- #define boostIO() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
- ll gcd(ll a, ll b) { return (b == 0 ? a : gcd(b, a % b)); }
- signed main() {
- int n, count = 0;
- ll mod = 1e9 + 7;
- string s;
- cin >> n >> s;
- for (auto ch : s) if (ch == '?') ++count;
- vector<vector<vector<ll>>> dp(n + 1, vector<vector<ll>>(4, vector<ll>(4)));
- vector<ll> v(n + 1, 1);
- for (int i = 1; i <= n; ++i) {
- v[i] = (v[i - 1] * 3) % mod;
- }
- dp[0][0][0] = 1;
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j <= 3; ++j) {
- for (int k = 0; k <= 3; ++k) {
- if (dp[i][j][k]) {
- dp[i + 1][j][k] += dp[i][j][k];
- dp[i + 1][j][k] %= mod;
- if (j < 3 && (s[i] == '?' || s[i] - 'a' == j)) {
- int nk = (s[i] == '?' ? k + 1 : k);
- dp[i + 1][j + 1][nk] += dp[i][j][k];
- dp[i + 1][j + 1][nk] %= mod;
- }
- }
- }
- }
- }
- ll ans = 0;
- for (int i = 0; i <= 3; ++i) {
- if (count >= i) {
- ans += (dp[n][3][i] * v[count - i]) % mod;
- ans %= mod;
- }
- }
- cout << ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement