#include #include #include using namespace std; typedef long long ll; const ll MOD = 1000000007; // 快速幂计算 (a^b) % MOD ll power(ll a, ll b) { ll res = 1; a %= MOD; while (b > 0) { if (b % 2 == 1) res = (res * a) % MOD; a = (a * a) % MOD; b /= 2; } return res; } /** * 构造逻辑: * 1. 题目中 candy 分发的规则符合 Parking Function 模型。 * 2. 在圆周上,任意固定大小为 (N-T) 的空置集合 E 的方案数均为 N^(T-1)。 * 3. 我们需要计算 (x, t, p) 的三元组数量,其中 x 是分发序列,t 是拍照时刻,p 是照片起始位置。 * 4. 对于固定的 p 和 t,符合照片 S 的方案数为: C(N-M, N-t-u) * N^(t-1),其中 u 是 S 中 'o' 的个数。 */ void solve() { ll N, M; if (!(cin >> N >> M)) return; string S; cin >> S; ll u = 0; for (char c : S) { if (c == 'o') u++; } // 核心项 N^(N-1) ll pow_N_N_minus_1 = power(N, N - 1); // 核心项 2^(N-M) -- 这是对所有可能的 t 求和后的组合数之和 ll pow_2_N_minus_M = power(2, N - M); ll term; if (u < M) { // 情况 A: 照片中至少有一个 '-'。 // 这意味着 t=0 时不可能匹配(因为 t=0 时全是 'o')。 // 此时 t 从 1 到 N 的求和正好覆盖了组合数 C(N-M, k) 的完整范围。 term = pow_2_N_minus_M; } else { // 情况 B: 照片 S 全是 'o' (u == M)。 // 这意味着 t=0 时初始状态(全空)也能匹配照片。 // t=0 贡献 N^N,而 t=1..N 贡献 (2^(N-M) - 1) * N^(N-1)。 // 合并后项为 (N + 2^(N-M) - 1)。 term = (pow_2_N_minus_M - 1 + N + MOD) % MOD; } // 合法照片起始位置 p 的数量:1 到 N-M+1 ll pos_count = (N - M + 1) % MOD; ll ans = (pos_count * term) % MOD; ans = (ans * pow_N_N_minus_1) % MOD; cout << ans << endl; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); solve(); return 0; }