結果
| 問題 |
No.2926 Botaoshi
|
| コンテスト | |
| ユーザー |
 Iroha_3856
|
| 提出日時 | 2024-10-12 15:10:23 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 23 ms / 2,000 ms |
| コード長 | 24,968 bytes |
| コンパイル時間 | 8,327 ms |
| コンパイル使用メモリ | 354,420 KB |
| 実行使用メモリ | 14,336 KB |
| 最終ジャッジ日時 | 2024-10-12 15:10:35 |
| 合計ジャッジ時間 | 10,093 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 42 |
ソースコード
//==========Iroha_3856's Library==========
//命名規則
//自作関数：ownFunction
//自作クラス：OwnClass
//#define _GLIBCXX_DEBUG
//STL
#include<bits/stdc++.h>
using namespace std;
//AtCoder-Library
#if __has_include(<atcoder/all>)
#include<atcoder/all>
using namespace atcoder;
using mint = atcoder::modint998244353;
#endif
//PBDS-tree
#if __has_include(<ext/pb_ds/assoc_container.hpp>)
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
using namespace __gnu_pbds;
template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//tree.find_by_order(k) = tree[k] (0-indexed)
//tree.order_of_key(k) = tree.lower_bound(k) - tree.begin()
//Note: Can only be used for non-multiple sets.
#endif
#define vec vector
#define ll long long
#define ull unsigned long long
#define vi vec<int>
#define vll vec<ll>
#define vb vec<bool>
#define vvi vec<vi>
#define vvll vec<vll>
#define vvb vec<vb>
#define vvvi vec<vvi>
#define vvvll vec<vvll>
#define vvvb vec<vvb>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pli pair<ll, int>
#define pq priority_queue
template<class T> using spq = priority_queue<T, vector<T>, greater<T>>;
#define eb emplace_back
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rep(i, l, r) for (int i=(int)(l); i<(int)(r); i++)
#define REP(i, l, r) for (int i=(int)(l); i<=(int)(r); i++)
#define siz(x) (int)x.size()
template<class T>bool chmax(T &a, T b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, T b) { if (b<a) { a=b; return 1; } return 0; }
//slice(A, l, r) = A[l, r)
template<class T>
vector<T> slice(const vector<T>& A, int l, int r) {
assert(0 <= l && l <= r && r <= (int)A.size());
vector<T> ret;
for (int i = l; i<r; i++) ret.push_back(A[i]);
return ret;
}
//slice(S, l, r) = S[l, r)
string slice(const string& S, int l, int r) {
assert(0 <= l && l <= r && r <= (int)S.size());
string ret;
for (int i = l; i<r; i++) ret += S[i];
return ret;
}
template<class T>
T allSum(vector<T> A) {
return reduce(A.begin(), A.end());
}
template<class T>
T allMax(vector<T> A) {
return *max_element(A.begin(), A.end());
}
template<class T>
T allMin(vector<T> A) {
return *min_element(A.begin(), A.end());
}
template<class T>
int allArgMax(vector<T> A) {
return max_element(A.begin(), A.end())-A.begin();
}
template<class T>
int allArgMin(vector<T> A) {
return min_element(A.begin(), A.end())-A.begin();
}
ll ceil(ll x, ll y) {
assert(y != 0);
if ((x >= 0) == (y >= 0)) {
return (abs(x) + abs(y)-1)/abs(y);
}
else {
return -(abs(x)/abs(y));
}
}
ll floor(ll x, ll y) {
assert(y != 0);
if ((x >= 0) == (y >= 0)) {
return abs(x)/abs(y);
}
else {
return -((abs(x) + abs(y)-1)/abs(y));
}
}
template<class T, class U>
istream &operator>>(istream &is, pair<T, U> &p) {
is >> p.first >> p.second;
return is;
}
template<class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
os << p.first << " " << p.second;
return os;
}
template <class T>
istream &operator>>(istream &is, vector<T> &v) {
for(auto &x : v) {
is >> x;
}
return is;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
for(int i = 0; i < (int)v.size(); i++) {
if(i != (int)v.size() - 1)
os << v[i] << " ";
else
os << v[i];
}
return os;
}
template<class T>
void print(T A, bool f = true) {
cerr << A;
if (f) cerr << endl;
}
template<class T, class U>
void print(pair<T, U> A, bool f = true) {
cerr << "{" << A.first << ", " << A.second << "}";
if (f) cerr << endl;
}
template<class T>
void print(vector<T> A, bool f = true) {
cerr << "{";
for (int i = 0; i<(int)A.size(); i++) {
print(A[i], false);
if (i+1 != (int)A.size()) cerr << ", ";
}
cerr << "}";
if (f) cerr << endl;
}
#define debug(x) cerr << #x << " = "; print(x)
struct IoSetup {
IoSetup() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << fixed << setprecision(15);
cerr << fixed << setprecision(15);
}
} iosetup;
struct Edge {
int to;
ll cost;
Edge(int to, ll cost) : to(to), cost(cost) {}
};
const int mod = 998244353;
const int MOD = 1000000007;
const int inf = 1000010000;
const ll INF = 4e18;
//グラフ入力
//無向重みなしグラフ
vector<vector<int>> graph(int& N, int& M) {
cin >> N >> M;
vector<vector<int>> G(N);
for (int i = 0; i < M; i++) {
int u, v; cin >> u >> v;
u--; v--;
G[u].push_back(v);
G[v].push_back(u);
}
return G;
}
//無向重み付きグラフ
vector<vector<Edge>> weightedGraph(int& N, int& M) {
cin >> N >> M;
vector<vector<Edge>> G(N);
for (int i = 0; i < M; i++) {
int u, v; ll w; cin >> u >> v >> w;
u--; v--;
G[u].push_back(Edge{v, w});
G[v].push_back(Edge{u, w});
}
return G;
}
//有向重みなしグラフ
vector<vector<int>> directedGraph(int& N, int& M) {
cin >> N >> M;
vector<vector<int>> G(N);
for (int i = 0; i < M; i++) {
int u, v; cin >> u >> v;
u--; v--;
G[u].push_back(v);
}
return G;
}
//有向重み付きグラフ
vector<vector<Edge>> weightedDirectedGraph(int& N, int& M) {
cin >> N >> M;
vector<vector<Edge>> G(N);
for (int i = 0; i < M; i++) {
int u, v; ll w; cin >> u >> v >> w;
u--; v--;
G[u].push_back(Edge{v, w});
}
return G;
}
//1次元累積和
//全て0-indexedで処理
template<class T>
struct ComulativeSum {
int siz;
vector<T> S;
bool done;
ComulativeSum() : ComulativeSum(0) {}
ComulativeSum(int N) : ComulativeSum(vector<T>(N, 0)) {}
//累積和の構築はしない
ComulativeSum(vector<T> A) {
done = false;
siz = (int)A.size();
S.resize(siz+1);
S[0] = 0;
for (int i = 0; i < siz; i++) {
S[i+1] = A[i];
}
}
//累積
void run() {
assert(!done);
for (int i = 1; i <= siz; i++) {
S[i] += S[i-1];
}
done = true;
}
//加算（累積前のみ）
T add(int idx, T a) {
assert(!done);
S[idx+1] += a;
return S[idx+1];
}
//代入（累積前のみ）
T set(int idx, T a) {
assert(!done);
S[idx+1] = a;
return S[idx+1];
}
//取得（累積前、累積後両方とも可能だが、どちらを想定するかをexpected_doneで渡す）
T get(int idx, bool expected_done) {
assert(expected_done == done);
return S[idx+1];
}
//区間和取得（累積後のみ）
//半開区間で与える
T sum(int l, int r) {
assert(done);
return S[r]-S[l];
}
};
template<class T>
struct ComulativeSum2D {
bool done;
int H, W;
vector<vector<T>> S;
ComulativeSum2D() : ComulativeSum2D(0, 0) {}
ComulativeSum2D(int h, int w) : ComulativeSum2D(vector<vector<T>>(h, vector<T>(w))) {}
ComulativeSum2D(vector<vector<T>> A) {
done = false;
H = (int)A.size();
W = (int)A[0].size();
S.resize(H+1, vector<T>(W+1, 0));
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) S[i+1][j+1] = A[i][j];
}
}
//累積
void run() {
assert(!done);
for (int i = 1; i <= H; i++) {
for (int j = 1; j <= W; j++) {
S[i][j] += S[i][j-1];
}
}
for (int j = 1; j <= W; j++) {
for (int i = 1; i <= H; i++) S[i][j] += S[i-1][j];
}
}
//加算（累積前のみ）
T add(int r, int c, T x) {
assert(!done);
S[r+1][c+1] += x;
}
//代入（累積前のみ）
T set(int r, int c, T x) {
assert(!done);
S[r+1][c+1] = x;
}
//取得（累積前、累積後両方とも可能だが、どちらを想定するかをexpected_doneで渡す）
T get(int r, int c, bool expect_done) {
assert(expect_done == done);
return S[r+1][c+1];
}
//区間和取得（累積後のみ）
//行、列とも半開区間で与える
T sum(int left_row, int right_row, int left_column, int right_column) {
return S[right_row][right_column]
- S[right_row][left_column]
- S[left_row][right_column]
+ S[left_row][left_column];
}
};
//よくつかうセグ木用の型宣言
//一点代入区間総和
namespace __RangeSumSegTree {
template<class T> T op(T a, T b) {return a + b;}
template<class T> T e() {return 0;}
};
template<class T>
using RangeSumSegTree = atcoder::segtree<T, __RangeSumSegTree::op<T>, __RangeSumSegTree::e<T>>;
//一点代入区間最小値
namespace __RangeMinSegTree {
template<class T> T op(T a, T b) {return min(a, b);}
template<class T, T __e> T e() {return __e;}
};
template<class T, T __e>
using RangeMinSegTree = atcoder::segtree<T, __RangeMinSegTree::op<T>, __RangeMinSegTree::e<T, __e>>;
//一点代入区間最大値
namespace __RangeMaxSegTree {
template<class T> T op(T a, T b) {return max(a, b);}
template<class T, T __e> T e() {return __e;}
};
template<class T, T __e>
using RangeMaxSegTree = atcoder::segtree<T, __RangeMaxSegTree::op<T>, __RangeMaxSegTree::e<T, __e>>;
//Union-Find
struct UnionFind {
vector<int> par, siz;
int connected_components;
UnionFind() {
init(0);
}
//n頂点0辺のグラフを作る
UnionFind(int n) {
init(n);
}
void init (int n) {
par.resize(n, -1);
siz.resize(n, 1);
connected_components = n;
}
//頂点xの連結成分の代表をreturnする
int root(int x) {
if (par[x]==-1) return x;
return par[x] = root(par[x]);
}
//頂点xと頂点yが同じ連結成分に属しているか判定する
bool same(int x, int y) {
return root(x)==root(y);
}
//頂点xと頂点yを結ぶ辺を作る
bool merge(int x, int y) {
x = root(x); y = root(y);
if (x==y) return false;
//siz[x] > siz[y]を前提とする
if (siz[x] < siz[y]) swap(x, y);
par[y] = x;
siz[x]+=siz[y];
connected_components--;
return true;
}
//頂点xの連結成分の頂点数をreturnする
int size(int x) {
return siz[root(x)];
}
int connectedComponents() {
return connected_components;
}
//これまでの頂点数をnとすると、頂点nを追加する（0-indexed）
//O(1)
void add_vertex() {
par.push_back(-1);
siz.push_back(1);
}
//これまでの頂点数をnとすると、vector<int> tosであらわされる辺を持った頂点nを追加する (0-indexed)
//O(tos.size())
void add_vertex(vector<int> tos) {
add_vertex();
int s = (int)par.size();
for (int to : tos) {
merge(s-1, to);
}
}
};
//重み付きUnion-Find
template<class T> struct WeightedUnionFind {
vector<int> par, siz;
vector<T> diff_weight;
WeightedUnionFind() : WeightedUnionFind(0) {}
WeightedUnionFind(int n) {
init(n);
}
void init(int n) {
par.resize(n, -1);
siz.resize(n, 1);
diff_weight.resize(n, 0);
}
int root(int x) {
if (par[x]==-1) return x;
int r = root(par[x]);
diff_weight[x] += diff_weight[par[x]];
return par[x] = r;
}
T weight(int x) {
root(x);
return diff_weight[x];
}
bool same(int x, int y) {
return root(x)==root(y);
}
//weight[y]-weight[x]=wとなるように辺を張る
bool merge(int x, int y, T w) {
w += weight(x); w -= weight(y);
x = root(x); y = root(y);
if (x == y) {
if (weight(y)-weight(x)==w) return true;
return false;
}
if (siz[x] < siz[y]) swap(x, y), w = -w;
par[y] = x;
diff_weight[y] = w;
return true;
}
};
//連結判定
//グラフGにおいて、startから頂点iが行けるかをvector<bool>で返す
vector<bool> connected(const vector<vector<int>>& G, int start) {
int N = (int)G.size();
stack<int> S;
vector<bool> seen(N, false);
S.push(start);
seen[start] = true;
while(!S.empty()) {
int pos = S.top(); S.pop();
for (int to : G[pos]) {
if (!seen[to]) {
seen[to] = true;
S.push(to);
}
}
}
return seen;
}
//BFS
//重みなしグラフにおける最短経路問題
vector<int> bfs(const vector<vector<int>> &G, int start, int impossible) {
queue<int> Q;
vector<int> dist((int)G.size(), impossible);
Q.push(start);
dist[start] = 0;
while(!Q.empty()) {
int pos = Q.front(); Q.pop();
for (int to : G[pos]) {
if (dist[to]!=impossible) continue;
Q.push(to);
dist[to] = dist[pos]+1;
}
}
return dist;
}
//dijkstra
//重み付きグラフにおける最短経路問題
vector<long long> dijkstra(const vector<vector<Edge>>& G, int start, long long impossible) {
int N = (int)G.size();
vector<long long> dist(N, impossible);
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> Q;
dist[start] = 0LL;
Q.emplace(dist[start], start);
while(!Q.empty()) {
pair<long long, int> pos = Q.top();
Q.pop();
long long d = pos.first;
int v = pos.second;
//trash
if (dist[v]!=impossible && dist[v]<d) continue;
for (Edge e : G[v]) {
if (dist[e.to]==impossible || dist[e.to]>d+e.cost) {
dist[e.to] = d+e.cost;
Q.push(make_pair(dist[e.to], e.to));
}
}
}
return dist;
}
//グリッド上でのBFS
//スタート位置の文字を与える
vector<vector<int>> gridBfs(const vector<string> &s, char start, const string wall, int impossible) {
const int vr[4] = {0, 1, 0, -1}, vc[4] = {1, 0, -1, 0};
vector<vector<int>> dist((int)s.size(), vector<int>(s[0].size(), impossible));
queue<pair<int, int>> Q;
//search start
for (int i = 0; i < (int)s.size(); i++) {
for (int j = 0; j < (int)s[0].size(); j++) {
if (s[i][j] == start) {
Q.emplace(i, j);
dist[i][j] = 0;
}
}
}
//BFS
while(!Q.empty()) {
pair<int, int> pos = Q.front(); Q.pop();
for (int i = 0; i < 4; i++) {
int nr = pos.first+vr[i], nc = pos.second+vc[i];
if (nr < 0 || nr >= (int)s.size() || nc < 0 || nc >= (int)s[0].size()) continue;
if (dist[nr][nc] != impossible) continue;
if (wall.find(s[nr][nc]) != string::npos) continue;
dist[nr][nc] = dist[pos.first][pos.second] + 1;
Q.emplace(nr, nc);
}
}
return dist;
}
//グリッド上でのBFS
//スタート位置の行、列を与える
vector<vector<int>> gridBfs(const vector<string> &s, int startrow, int startcolumn, const string wall, int impossible) {
const int vr[4] = {0, 1, 0, -1}, vc[4] = {1, 0, -1, 0};
vector<vector<int>> dist((int)s.size(), vector<int>(s[0].size(), impossible));
queue<pair<int, int>> Q;
Q.emplace(startrow, startcolumn);
dist[startrow][startcolumn] = 0;
//BFS
while(!Q.empty()) {
pair<int, int> pos = Q.front(); Q.pop();
for (int i = 0; i < 4; i++) {
int nr = pos.first+vr[i], nc = pos.second+vc[i];
if (nr < 0 || nr >= (int)s.size() || nc < 0 || nc >= (int)s[0].size()) continue;
if (dist[nr][nc] != impossible) continue;
if (wall.find(s[nr][nc]) != string::npos) continue;
dist[nr][nc] = dist[pos.first][pos.second] + 1;
Q.emplace(nr, nc);
}
}
return dist;
}
//MST
//{辺長, u, v} の vector<tuple<ll, int, int>> を渡す
long long mst(vector<tuple<long long, int, int>> E, int N, bool m) {
int M = (int)E.size();
if (!m) sort(E.begin(), E.end());
else sort(E.begin(), E.end(), greater<tuple<long long, int, int>>());
dsu d(N);
long long ret = 0;
for (int i=0; i<M; i++) {
if (!d.same(get<1>(E[i]), get<2>(E[i]))) {
ret+=(long long) get<0>(E[i]);
d.merge(get<1>(E[i]), get<2>(E[i]));
}
}
return ret;
}
//DAG判定
bool isDAG(const vector<vector<int>>& G) {
int V = (int)G.size();
vector<int> deg(V, 0);
rep(i, 0, V) {
for (int to : G[i]) deg[to]++;
}
queue<int> Q;
rep(i, 0, V) if (deg[i] == 0) Q.push(i);
vector<bool> ans(V, false);
while(!Q.empty()) {
int v = Q.front(); Q.pop();
ans[v] = true;
for (int to : G[v]) {
deg[to]--;
if (deg[to] == 0) Q.push(to);
}
}
bool k = true;
rep(i, 0, V) if (!ans[i]) k = false;
return k;
}
//トポロジカルソート
//入次数が0の頂点が最初に来る
bool topologicalSort(const vector<vector<int>>& G, vector<int>& res) {
assert(res.empty());
int V = (int)G.size();
vector<int> deg(V);
rep(i, 0, V) {
for (int to : G[i]) deg[to]++;
}
queue<int> Q;
rep(i, 0, V) {
if (deg[i] == 0) Q.push(i);
}
while(!Q.empty()) {
int v = Q.front(); Q.pop();
res.push_back(v);
for (int to : G[v]) {
deg[to]--;
if (deg[to] == 0) Q.push(to);
}
}
if ((int)res.size() != V) {
res.clear();
return false;
}
return true;
}
//素数判定
bool isPrime(long long N) {
for (long long d = 2; d * d <= N; d++) {
if (N%d == 0) return false;
}
return true;
}
//エラトステネスの篩による [1, N] の素数判定
vector<bool> primeSieve(int N) {
vector<bool> isPrime(N+1);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i <= N; i++) {
if (isPrime[i]) {
for (int j = 2*i; j <= N; j += i) isPrime[j] = false;
}
}
return isPrime;
}
//最小素因数 (Least Prime Factor)
long long lpf(long long N) {
for (long long d = 2; d * d <= N; d++) {
if (N%d == 0) {
return d;
}
}
return N;
}
//エラトステネスの篩による [1, N] の最小素因数
vector<int> lpfSieve(int N) {
vector<int> lpf(N+1);
iota(lpf.begin(), lpf.end(), 0);
lpf[0] = lpf[1] = -1;
for (int i = 2; i <= N; i++) {
if (lpf[i] == i) {
for (int j = 2*i; j <= N; j += i) {
lpf[j] = min(lpf[j], i);
}
}
}
return lpf;
}
//N の 素因数分解
//{p, e} of N を返す
vector<pair<long long, int>> primeFactorization(long long N) {
vector<pair<long long, int>> ret;
for (long long d = 2; d * d <= N; d++) {
if (N%d) continue;
int cnt = 0;
while(N%d == 0) {
cnt++;
N /= d;
}
ret.push_back({d, cnt});
}
return ret;
}
//[1, N] の素因数分解
//[1, N] の lpf 配列を与えて、{{p, e} of 0, {p, e} of 1, ... , {p, e} of N} を返す
//0, 1は空
vector<vector<pair<int, int>>> primeFactorization(vector<int> lpf) {
int N = (int)lpf.size()-1;
vector<vector<pair<int, int>>> ret(N+1);
for (int i = 2; i <= N; i++) {
if (lpf[i] == i) ret[i] = {{i, 1}};
else {
ret[i] = ret[i/lpf[i]];
if (ret[i].back().first == lpf[i]) {
ret[i].back().second++;
}
else ret[i].push_back({lpf[i], 1});
}
}
return ret;
}
struct combination {
vector<mint> fac, infac;
combination(int n) {
fac.resize(n+1);
infac.resize(n+1);
fac[0] = 1;
for (int i = 1; i <= n; i++) fac[i] = fac[i-1] * i;
infac[n] = fac[n].inv();
for (int i = n; i >= 1; i--) infac[i-1] = infac[i] * i;
}
mint operator()(int n, int k) {
if (k < 0 || k > n) return 0;
return fac[n] * infac[k] * infac[n-k];
}
};
struct Hash {
vector<long long> mod = {998244353, 1000000007, 1000000009, 1000000021, 1000000033};
#ifdef const_rand
long long K = const_rand;
#else
long long K = 100 + rand()%100;
#endif
vector<vector<long long>> Pow;
//H[i] = Hash[0, i)
vector<vector<long long>> H;
int B = 5;
vector<int> S;
int N;
void init(string s) {
N = (int)s.size();
S.resize(N);
for (int i = 0; i<N; i++) {
if (islower(s[i])) S[i] = s[i]-'a' + 1;
if (isupper(s[i])) S[i] = s[i]-'A' + 27;
}
Pow.resize(B, vector<long long>(N+1));
for (int i = 0; i<B; i++) {
Pow[i][0] = 1;
for(int j = 1; j<N+1; j++) {
Pow[i][j] = Pow[i][j-1] * K;
Pow[i][j] %= mod[i];
}
}
H.resize(B);
for (int i = 0; i<B; i++) {
H[i].resize(N+1);
H[i][0] = 0;
for (int j = 1; j<N+1; j++) {
H[i][j] = (H[i][j-1] * K + S[j-1])%mod[i];
}
}
}
Hash() {
init("");
}
Hash(string s) {
init(s);
}
Hash(string s, vector<long long> m) {
mod = m;
B = (int)m.size();
init(s);
}
//val(l, r) = Hash[l, r)
vector<long long> val(int l, int r) {
vector<long long> res(B);
for (int i = 0; i<B; i++) {
res[i] = H[i][r] - (Pow[i][r-l] * H[i][l]%mod[i]);
if (res[i] < 0) res[i] += mod[i];
}
return res;
}
//same(l1, r1, l2, r2) = issame(S[l1, r1), S[l2, r2))
bool same(int l1, int r1, int l2, int r2) {
if (val(l1, r1) == val(l2, r2)) return true;
return false;
}
};
/*
created by drken
https://qiita.com/drken/items/b97ff231e43bce50199a
返り値: a と b の最大公約数
ax + by = gcd(a, b) を満たす (x, y) が格納される
＜補足＞
(a, b) = (0, 2), (-1, -3)など、a<=0, b<=0の場合でも動きます。
ただし、返ってくるgcdが負になることがあることに注意
gcdが0になるのは(a, b) = (0, 0)の場合のみです
(a, b) = (0, 2)などの場合はちゃんと2となって返ってきます
*/
long long extGCD(long long a, long long b, long long &x, long long &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
long long d = extGCD(b, a%b, y, x);
y -= a/b * x;
return d;
}
vector<pair<char, int>> runLength(const string& S) {
int N = (int)S.size();
vector<pair<char, int>> ret;
for (int l = 0; l<N;) {
int r = l+1;
for (; r<N && S[l]==S[r] && S[r]=='='; r++) ;
ret.emplace_back(S[l], r-l);
l = r;
}
return ret;
}
string runLengthDecode(const vector<pair<char, int>>& code) {
string ret = "";
for (pair<char, int> c : code) {
ret+=string(c.first, c.second);
}
return ret;
}
int digitSum(long long T) {
string t = to_string(T);
int ret = 0;
for (char k : t) ret+=k-'0';
return ret;
}
template<class T>
vector<int> compress(const vector<T>& A) {
vector<T> B = A;
sort(B.begin(), B.end());
B.erase(unique(B.begin(), B.end()), B.end());
vector<int> res((int)A.size());
for (int i = 0; i < (int)A.size(); i++) {
res[i] = lower_bound(B.begin(), B.end(), A[i])-B.begin();
}
return res;
}
//vector<T>であらわされるn進数を10進数に変換する
template<class T>
T changeBaseToTen(const vector<T>& A, T n) {
T ret = 0;
T mul = 1;
for (int i = (int)A.size()-1; i >= 0; i--) {
ret += mul * A[i];
mul *= n;
}
return ret;
}
//10進数でxのものをn進数に変換する
template<class T>
vector<T> changeBaseFromTen(T x, T n) {
vector<T> ret;
while(x != 0) {
ret.push_back(x%n);
x /= n;
}
reverse(ret.begin(), ret.end());
return ret;
}
//n進法の桁のvectorであるSをm進法に変換する
template<class T>
vector<T> changeBase(const vector<T>& S, T n, T m) {
T ten = changeBaseToTen(S, n);
return changeBaseTromTen(ten, m);
}
int main() {
int N; string S; cin >> N >> S;
vector<vector<mint>> dp(N+1, vector<mint>(3));
dp[0][0] = 1;
//0 : U
//1 : L
//2 : R
string T = "ULR";
rep(i, 0, N) {
rep(j, 0, 3) {
rep(k, 0, 3) {
if (j == 2 and k == 1) continue;
if (S[i] != '.' and T[k] != S[i]) continue;
dp[i+1][k] += dp[i][j];
}
}
}
mint ans = dp[N][0] + dp[N][1] + dp[N][2];
cout << ans.val() << endl;
}