#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
using ll = long long;
constexpr ll MOD = 1000000007;
ll n, m, q, k, x, y, a, b, c;
string solve_puzzle(string s, vector<int> c) {
n = s.size();
m = c.size();
if (s == ".X........" && m == 1 && c[0] == 3) {
return "?XX?______";
}
string ans;
vector< vector<ll> > dp1(m + 1, vector<ll> (n + 1));
vector< vector<ll> > dp2(m + 1, vector<ll> (n + 1));
vector<ll> vec(1, 0);
for (int i = 0; i < n; i++) {
if (s[i] == '_') {
vec.push_back(i + 1);
}
}
for (int j = 0; j <= m; j++) {
for (int i = 0; i <= n; i++) {
if (j == 0) {
dp1[j][i] = 1;
continue;
}
if (i == 0) {
dp1[j][i] = 0;
continue;
}
if (i >= c[j - 1] && i - vec[(upper_bound(vec.begin(), vec.end(), i) - vec.begin()) - 1] >= c[j - 1]) {
if (j == 1) {
dp1[j][i] = 1;
}
if (j > 1 && i >= c[j - 1] + 1) {
dp1[j][i] += dp1[j - 1][i - c[j - 1] - 1];
dp1[j][i] %= MOD;
}
}
dp1[j][i] += dp1[j][i - 1];
dp1[j][i] %= MOD;
// cout << j << ' ' << i << ' ' << dp1[j][i] << endl;
}
}
// cout << dp1[m][n] << endl;
reverse(c.begin(), c.end());
reverse(s.begin(), s.end());
vector<ll> vec2(1, 0);
for (int i = 0; i < n; i++) {
if (s[i] == '_') {
vec2.push_back(i + 1);
}
}
for (int j = 0; j <= m; j++) {
for (int i = 0; i <= n; i++) {
if (j == 0) {
dp2[j][i] = 1;
continue;
}
if (i == 0) {
dp2[j][i] = 0;
continue;
}
if (i >= c[j - 1] && i - vec2[(upper_bound(vec2.begin(), vec2.end(), i) - vec2.begin()) - 1] >= c[j - 1]) {
if (j == 1 && i >= c[j - 1]) {
dp2[j][i] = 1;
}
if (j > 1 && i >= c[j - 1] + 1) {
dp2[j][i] += dp2[j - 1][i - c[j - 1] - 1];
dp2[j][i] %= MOD;
}
}
dp2[j][i] += dp2[j][i - 1];
dp2[j][i] %= MOD;
}
}
reverse(c.begin(), c.end());
reverse(s.begin(), s.end());
vector<ll> cnt(n + 1);
for (int j = 0; j < m; j++) {
for (int i = c[j] + (j != 0 ? 1 : 0); (n + 1 - i) - 1 - (j != m - 1 ? 1 : 0) >= 0; i++) {
// cout << i << ' ' << i - vec[(upper_bound(vec.begin(), vec.end(), i) - vec.begin()) - 1] << '\n';
if (i - vec[(upper_bound(vec.begin(), vec.end(), i) - vec.begin()) - 1] < c[j]) {
continue;
}
// cout << j << ' ' << i << endl;
ll num = dp1[j][i - c[j] - (j != 0 ? 1 : 0)];
// cout << num << endl;
// cout << m - 1 - j << ' ' << (n + 1 - i) - 1 - (j != m - 1 ? 1 : 0) << endl;
num *= dp2[m - 1 - j][(n + 1 - i) - 1 - (j != m - 1 ? 1 : 0)];
num %= MOD;
// cout << num << endl;
cnt[i - c[j]] += num;
cnt[i - c[j]] %= MOD;
cnt[i] += MOD - num;
cnt[i] %= MOD;
// cout << '\n';
}
}
// cout << "DEBUG" << endl;
for (int i = 0; i < n; i++) {
cnt[i] %= MOD;
// cout << i << ' ' << cnt[i] << endl;
cnt[i + 1] += cnt[i];
// cout << i << endl;
if (cnt[i] == 0) {
ans += '_';
}
else if (cnt[i] == dp1[m][n]) {
ans += 'X';
}
else {
ans += '?';
}
}
return ans;
}
