#include <vector>
#include <iostream>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <tuple>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <complex>
#include <iterator>
#include <array>
#include <memory>
#include <random>
//cin.sync_with_stdio(false);
//streambuf
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
using vi = vector<int>;
using vll = vector<ll>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using ti3 = tuple<int, int, int>;
using vti3 = vector<ti3>;
template<class T, int s>using va = vector<array<T, s>>;
template<class T, class T2> using umap = unordered_map<T, T2>;
template<class T> using uset = unordered_set<T>;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
#define ALL(a) a.begin(),a.end()
#define rep(i,a) for(int i=0;i<a;i++)
#define rep1(i,a) for(int i=1;i<=a;i++)
#define rrep(i,a) for(int i=(a)-1;i>=0;i--)
#define rrep1(i,a) for(int i=a;i;i--)
const ll mod = 1000000007;
#define REP rep
template<class T>using heap = priority_queue<T, vector<T>, greater<T>>;
template<class T>using pque = priority_queue<T, vector<T>, function<T(T, T)>>;
template <class T>
inline void hash_combine(size_t & seed, const T & v) {
	hash<T> hasher;
	seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
namespace std {
	template<typename S, typename T> struct hash<pair<S, T>> {
		inline size_t operator()(const pair<S, T> & v) const {
			size_t seed = 0;
			hash_combine(seed, v.first);
			hash_combine(seed, v.second);
			return seed;
		}
	};
	// Recursive template code derived from Matthieu M.
	template <class Tuple, size_t Index = std::tuple_size<Tuple>::value - 1>
	struct HashValueImpl{
		static void apply(size_t& seed, Tuple const& tuple){
			HashValueImpl<Tuple, Index - 1>::apply(seed, tuple);
			hash_combine(seed, std::get<Index>(tuple));
		}
	};
	template <class Tuple>
	struct HashValueImpl<Tuple, 0>{
		static void apply(size_t& seed, Tuple const& tuple){
			hash_combine(seed, std::get<0>(tuple));
		}
	};
	template <typename ... TT>
	struct hash<std::tuple<TT...>>{
		size_t operator()(std::tuple<TT...> const& tt) const{
			size_t seed = 0;
			HashValueImpl<std::tuple<TT...> >::apply(seed, tt);
			return seed;
		}
	};
}
template<class T>int id(vector<T> &a, T b) {
	return lower_bound(ALL(a), b) - a.begin();
}
ll pow(ll base, ll i, ll mod) {
	ll a = 1;
	while (i) {
		if (i & 1) {
			a *= base;
			a %= mod;
		}
		base *= base;
		base %= mod;
		i /= 2;
	}
	return a;
}
ll gcd(ll a, ll b) {
	while (b) {
		ll c = a%b;
		a = b;
		b = c;
	}
	return a;
}
ll lcm(ll a, ll b) {
	return a / gcd(a, b)*b;
}
int popcnt(unsigned long long a) {
	a = (a & 0x5555555555555555) + (a >> 1 & 0x5555555555555555);
	a = (a & 0x3333333333333333) + (a >> 2 & 0x3333333333333333);
	a = (a & 0x0f0f0f0f0f0f0f0f) + (a >> 4 & 0x0f0f0f0f0f0f0f0f);
	a = (a & 0x00ff00ff00ff00ff) + (a >> 8 & 0x00ff00ff00ff00ff);
	a = (a & 0x0000ffff0000ffff) + (a >> 16 & 0x0000ffff0000ffff);
	return (a & 0xffffffff) + (a >> 32);
}
class unionfind {
	vector<int> par, rank, size_;//????????§??????????????¢???????????????????????????rank???????????????size?????????
public:
	unionfind(int n) :par(n), rank(n), size_(n, 1) {
		iota(ALL(par), 0);
	}
	int find(int x) {
		if (par[x] == x)return x;
		return par[x] = find(par[x]);
	}
	void unite(int x, int y) {
		x = find(x), y = find(y);
		if (x == y)return;
		if (rank[x] < rank[y])swap(x, y);
		par[y] = x;
		size_[x] += size_[y];
		if (rank[x] == rank[y])rank[x]++;
	}
	bool same(int x, int y) {
		return find(x) == find(y);
	}
	int size(int x) {
		return size_[find(x)];
	}
};
template<class T, class Func = function<T(T, T)>>
class segtree {
	vector<T> obj;
	int offset;
	Func updater;
	T e;
	int bufsize(int num) {
		int i = 1;
		for (; num >i; i <<= 1);
		offset = i - 1;
		return (i << 1) - 1;
	}
	T query(int a, int b, int k, int l, int r) {
		if (r <= a || b <= l)return e;
		if (a <= l && r <= b)return obj[k];
		else return updater(query(a, b, k * 2 + 1, l, (l + r) / 2), query(a, b, k * 2 + 2, (l + r) / 2, r));
	}
	/*
	template<class QF = function<T(T, T)>>
	auto query(int a, int b, int k, int l, int r,QF qf) {
		if (r <= a || b <= l)return e;
		if (a <= l && r <= b)return obj[k];
		else return qf(query(a, b, k * 2 + 1, l, (l + r) / 2, qf), query(a, b, k * 2 + 2, (l + r) / 2, r, qf));
	}*/
public:
	T query(int a, int b) {//[a,b)
		return query(a, b, 0, 0, offset + 1);
	}/*
	template<class QF = function<T(T, T)>>
	auto query(int a, int b,QF &&qf) {//[a,b)
		return query(a, b, 0, 0, offset + 1,qf);
	}*/
	void updateall(int l = 0, int r = -1) {
		if (r < 0)r = offset + 1;
		l += offset, r += offset;
		do {
			l = l - 1 >> 1, r = r - 1 >> 1;
			for (int i = l; i < r; i++)obj[i] = updater(obj[i * 2 + 1], obj[i * 2 + 2]);
		} while (l);
	}
	void update(int k, T &a) {
		k += offset;
		obj[k] = a;
		while (k) {
			k = k - 1 >> 1;
			obj[k] = updater(obj[k * 2 + 1], obj[k * 2 + 2]);
		}
	}
	segtree(int n, T e, const Func &updater = Func()) :obj(bufsize(n), e), e(e), updater(updater) {}
	segtree(vector<T> &vec, T e, const Func &updater = Func()) :obj(bufsize(vec.size()), e), e(e), updater(updater) {
		copy(vec.begin(), vec.end(), obj.begin() + offset);
		updateall();
	}
	typename vector<T>::reference operator[](int n) {
		return obj[n + offset];
	}
};
template<class T = int>
class BIT {//????¬????BIT????????????????????????????????°??????????????????
	vector<T> bit;
	int n;
public:
	BIT(int n) :bit(n + 1, 0) {}
	void add(int i, T x) {
		i++;
		while (i <= n) {
			bit[i] += x;
			i += i&-i;
		}
	}
	T sum(int i) {
		T s = 0;
		i++;
		while (i) {
			s += bit[i];
			i &= i - 1;
		}
		return s;
	}
};
template<class T = int>
class rangeadd {
	BIT<T> b0, b1;
public:
	rangeadd(int n) :b0(n), b1(n) {};
	void add(int l, int r, T x) {//[l,r)
		b0.add(l, -x*(l - 1));
		b1.add(l, x);
		b0.add(r, x*r);
		b1.add(r, -x);
	}
	T sum(int i) {
		if (i < 0)return 0;
		return b0.sum(i) + b1.sum(i)*i;
	}
	T sum(int l,int r) {
		return sum(r - 1) - sum(l - 1);
	}
};
typedef complex<ld> P;
typedef vector<P> VP;
const ld eps = 1e-11, pi = acos(-1.0);

ld dot(P a, P b) { return real(conj(a) * b); }
ld cross(P a, P b) { return imag(conj(a) * b); }

namespace std {
	bool operator<(const P &a, const P &b) {
		return abs(a.real() - b.real()) < eps ? a.imag() < b.imag() : a.real() < b.real();
	}
}

struct L { P a, b; };//line->l,segment->s
struct C { P p; ld r; };

int ccw(P a, P b, P c) {
	b -= a; c -= a;
	if (cross(b, c) > eps) return 1;   // counter clockwise
	if (cross(b, c) < -eps) return -1; // clockwise
	if (dot(b, c) < 0) return 2;       // c--a--b on line
	if (norm(b) < norm(c)) return -2;  // a--b--c on line
	return 0;                          // a--c--b on line
}

bool isis_ll(L l, L m) {//is intersect
	return abs(cross(l.b - l.a, m.b - m.a)) > eps;
}

bool isis_ls(L l, L s) {
	ld a = cross(l.b - l.a, s.a - l.a);
	ld b = cross(l.b - l.a, s.b - l.a);
	return (a * b < eps);
}

bool isis_lp(L l, P p) {
	return abs(cross(l.b - p, l.a - p)) < eps;
}

bool isis_ss(L s, L t) {
	return ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) <= 0 &&
		ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) <= 0;
}

P is_ll(L s, L t) { //intersect
	P sv = s.b - s.a, tv = t.b - t.a;
	return s.a + sv * cross(tv, t.a - s.a) / cross(tv, sv);
}

bool isis_sp(L s, P p) {
	return abs(s.a - p) + abs(s.b - p) - abs(s.b - s.a) < eps;
}

P proj(L l, P p) {
	ld t = dot(p - l.a, l.a - l.b) / norm(l.a - l.b);
	return l.a + t * (l.a - l.b);
}

ld dist_lp(L l, P p) {
	return abs(p - proj(l, p));
}

ld dist_ll(L l, L m) {
	return isis_ll(l, m) ? 0 : dist_lp(l, m.a);
}

ld dist_ls(L l, L s) {
	if (isis_ls(l, s)) return 0;
	return min(dist_lp(l, s.a), dist_lp(l, s.b));
}

ld dist_sp(L s, P p) {
	P r = proj(s, p);
	if (isis_sp(s, r)) return abs(r - p);
	return min(abs(s.a - p), abs(s.b - p));
}

ld dist_ss(L s, L t) {
	if (isis_ss(s, t)) return 0;
	ld a = min(dist_sp(s, t.a), dist_sp(t, s.a));
	ld b = min(dist_sp(s, t.b), dist_sp(t, s.b));
	return min(a, b);
}

VP is_cc(C c1, C c2) {
	VP res;
	ld d = abs(c1.p - c2.p);
	ld rc = (d * d + c1.r * c1.r - c2.r * c2.r) / (2 * d);
	ld dfr = c1.r * c1.r - rc * rc;
	if (abs(dfr) < eps) dfr = 0.0;
	else if (dfr < 0.0) return res; // no intersection
	ld rs = sqrt(dfr);
	P diff = (c2.p - c1.p) / d;
	res.push_back(c1.p + diff * P(rc, rs));
	if (dfr != 0.0) res.push_back(c1.p + diff * P(rc, -rs));
	return res;
}

bool isis_vc(vector<C> vc) {
	VP crs;
	int n = vc.size();
	rep(i, n)rep(j, i)
		for (P p : is_cc(vc[i], vc[j]))
			crs.push_back(p);
	rep(i, n)
		crs.push_back(vc[i].p);
	for (P p : crs) {
		bool valid = true;
		rep(i, n)
			if (abs(p - vc[i].p)>vc[i].r + eps)
				valid = false;
		if (valid) return true;
	}
	return false;
}

VP is_lc(C c, L l) {
	VP res;
	ld d = dist_lp(l, c.p);
	if (d < c.r + eps) {
		ld len = (d > c.r) ? 0.0 : sqrt(c.r * c.r - d * d); //safety;
		P nor = (l.a - l.b) / abs(l.a - l.b);
		res.push_back(proj(l, c.p) + len * nor);
		res.push_back(proj(l, c.p) - len * nor);
	}
	return res;
}

VP is_sc(C c, L l) {
	VP v = is_lc(c, l), res;
	for (P p : v)
		if (isis_sp(l, p)) res.push_back(p);
	return res;
}

vector<L> tangent_cp(C c, P p) {//????????\????
	vector<L> ret;
	P v = c.p - p;
	ld d = abs(v);
	ld l = sqrt(norm(v) - c.r * c.r);
	if (isnan(l)) { return ret; }
	P v1 = v * P(l / d, c.r / d);
	P v2 = v * P(l / d, -c.r / d);
	ret.push_back(L{ p, p + v1 });
	if (l < eps) return ret;
	ret.push_back(L{ p, p + v2 });
	return ret;
}

vector<L> tangent_cc(C c1, C c2) {
	vector<L> ret;
	if (abs(c1.p - c2.p) - (c1.r + c2.r) > -eps) {
		P center = (c1.p * c2.r + c2.p * c1.r) / (c1.r + c2.r);
		ret = tangent_cp(c1, center);
	}
	if (abs(c1.r - c2.r) > eps) {
		P out = (-c1.p * c2.r + c2.p * c1.r) / (c1.r - c2.r);
		vector<L> nret = tangent_cp(c1, out);
		ret.insert(ret.end(), ALL(nret));
	}
	else {
		P v = c2.p - c1.p;
		v /= abs(v);
		P q1 = c1.p + v * P(0, 1) * c1.r;
		P q2 = c1.p + v * P(0, -1) * c1.r;
		ret.push_back(L{ q1, q1 + v });
		ret.push_back(L{ q2, q2 + v });
	}
	return ret;
}

ld area(const VP &p) {//??¢?????
	ld res = 0;
	int n = p.size();
	rep(j, n) res += cross(p[j], p[(j + 1) % n]);
	return res / 2;
}

bool is_polygon(L l, VP &g) {
	int n = g.size();
	for (int i = 0; i < n; i++) {
		P a = g[i];
		P b = g[(i + 1) % n];
		if (isis_ss(l, L{ a, b })) return true;
	}
	return false;
}

int is_in_Polygon(const VP &g, P p) {
	bool in = false;
	int n = g.size();
	for (int i = 0; i < n; i++) {
		P a = g[i] - p, b = g[(i + 1) % n] - p;
		if (imag(a) > imag(b)) swap(a, b);
		if (imag(a) <= 0 && 0 < imag(b))
			if (cross(a, b) < 0) in = !in;
		if (abs(cross(a, b)) < eps && dot(a, b) < eps) return 0; // on
	}
	if (in) return 1; // in
	return -1; // out
}

VP ConvexHull(VP ps) {
	int n = ps.size();
	int k = 0;
	sort(ps.begin(), ps.end());
	VP ch(2 * n);
	for (int i = 0; i < n; ch[k++] = ps[i++])
		while (k >= 2 && ccw(ch[k - 2], ch[k - 1], ps[i]) <= 0) --k;
	for (int i = n - 2, t = k + 1; i >= 0; ch[k++] = ps[i--])
		while (k >= t && ccw(ch[k - 2], ch[k - 1], ps[i]) <= 0) --k;
	ch.resize(k - 1);
	return ch;
}

VP ConvexCut(const VP &ps, L l) {
	VP Q;
	for (int i = 0; i < (int)ps.size(); i++) {
		P A = ps[i], B = ps[(i + 1) % ps.size()];
		if (ccw(l.a, l.b, A) != -1) Q.push_back(A);
		if (ccw(l.a, l.b, A) * ccw(l.a, l.b, B) < 0)
			Q.push_back(is_ll(L{ A, B }, l));
	}
	return Q;
}
class Flow {
	int V;
	struct edge { int to, cap, rev, cost; };
	vector<vector<edge>> G;
	vector<int> level, iter, h, dist, prevv, preve;
public:
	Flow(int size) :G(size + 1), V(size + 1) {
	}
	void add_edge(int from, int to, int cap, int cost = 0) {
		G[from].push_back(edge{ to, cap, (int)G[to].size(),cost });
		G[to].push_back(edge{ from,0,(int)G[from].size() - 1,-cost });
	}
	void bfs(int s) {
		fill(level.begin(), level.end(), -1);
		queue<int> que;
		level[s] = 0;
		que.push(s);
		while (!que.empty()) {
			int v = que.front(); que.pop();
			for (int i = 0; i < G[v].size(); i++) {
				edge &e = G[v][i];
				if (e.cap > 0 && level[e.to] < 0) {
					level[e.to] = level[v] + 1;
					que.push(e.to);
				}
			}
		}
	}
	int dfs(int v, int t, int f) {
		if (v == t)return f;
		for (int &i = iter[v]; i < G[v].size(); i++) {
			edge &e = G[v][i];
			if (e.cap > 0 && level[v] < level[e.to]) {
				int d = dfs(e.to, t, min(f, e.cap));
				if (d > 0) {
					e.cap -= d;
					G[e.to][e.rev].cap += d;
					return d;
				}
			}
		}
		return 0;
	}
	int max_flow(int s, int t) {
		level.resize(V);
		iter.resize(V);
		int flow = 0;
		for (;;) {
			bfs(s);
			if (level[t] < 0)return flow;
			fill(iter.begin(), iter.end(), 0);
			int f;
			while ((f = dfs(s, t, numeric_limits<int>::max()))>0) {
				flow += f;
			}
		}
	}
	typedef pair<int, int> P;
	int min_cost_flow(int s, int t, int f) {
		int res = 0;
		h.resize(V);
		dist.resize(V);
		prevv.resize(V);
		preve.resize(V);
		fill(h.begin(), h.end(), 0);
		while (f > 0) {
			priority_queue<P, vector<P>, greater<P>> que;
			fill(dist.begin(), dist.end(), numeric_limits<int>::max());
			dist[s] = 0;
			que.push({ 0,s });
			while (!que.empty()) {
				P p = que.top(); que.pop();
				int v = p.second;
				if (dist[v] < p.first)continue;
				for (int i = 0; i < G[v].size(); i++) {
					edge &e = G[v][i];
					if (e.cap > 0 && dist[e.to]>dist[v] + e.cost + h[v] - h[e.to]) {
						dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
						prevv[e.to] = v;
						preve[e.to] = i;
						que.push({ dist[e.to],e.to });
					}
				}
			}
			if (dist[t] == numeric_limits<int>::max()) {
				return -1;
			}
			for (int v = 0; v < V; v++)h[v] += dist[v];

			int d = f;
			for (int v = t; v != s; v = prevv[v]) {
				d = min(d, G[prevv[v]][preve[v]].cap);
			}
			f -= d;
			res += d*h[t];
			for (int v = t; v != s; v = prevv[v]) {
				edge &e = G[prevv[v]][preve[v]];
				e.cap -= d;
				G[v][e.rev].cap += d;
			}
		}
		return res;
	}
};
//end of lib
//template<class S=void,int ptr_num, class T = char>class trie {
//	umap<T, trie<S, ptr_num, T> next;
//public:
//	S key;
//	trie<S, ptr_num, T>* ptr[ptr_num] = {};
//	trie(S &&data) :key(data) {}
//	trie(const S &data) :key(data) {}
//	void add(T x,S data) {
//		if (!next.find(x))next.insert(x, data);
//	}
//	trie& operator[](T x) {
//		return next[x];
//	}
//	bool find(T x) {
//		retun next.find(x);
//	}
//};
//template<class T=char>class AhoCorasick {
//	trie<pair<bool,int>, 2, T> tree;
//	AhoCorasick(vector<string> p) {
//		int num = 0;
//		vector<decltype(&tree)> que(p.size(),&tree);
//		for (int i = 0;; i++) {
//			bool end = 1;
//			int i = 0;
//			for (auto a : p) {
//				if (i >= a.size())break;
//				end = ;0
//				que[i] = (*que[i])[a[i]];
//				i++;
//			}
//			if (end)break;
//		}
//	}
//};
class Lowlink {
	vector<vector<int>> G;
	vector<int> order;
	vector<pair<int, int>> bridge_;
	vector<int> articulation_;
	int next = 0;
	int dfs(int v, int prev) {
		int res = order[v] = next++;
		bool is_articulation = 0;
		int d = 0;
		for (auto to : G[v]) {
			if (to == prev)continue;
			if (order[to] >= 0)res = min(res, order[to]);
			else {
				int low = dfs(to, v);
				if (low > order[v])bridge_.emplace_back(v, to);
				if (prev >= 0 && low >= order[v])is_articulation = 1;
				res = min(res, low);
				d++;
			}
		}
		if (prev < 0 && d >= 2)is_articulation = 1;
		if (is_articulation)articulation_.push_back(v);
		return res;
	}
public:
	Lowlink(int size) :G(size + 1) {}
	void add_edge(int from, int to) {
		G[from].push_back(to);
	}
	void solve(int start = 0) {
		dfs(start, -1);
	}
	const auto& bridge() {
		return bridge_;
	}
	const auto& articulation() {
		return articulation_;
	}
};
class SCC {
	int V;
	int solved = -1;
	vector<vector<int>> G, rG;
	vector<int> vs;
	vector<char> used;
	vector<int> cmp;
	void dfs(int v) {
		used[v] = 1;
		for (auto a : G[v])if (!a)dfs(a);
		vs.push_back(v);
	}
	void rdfs(int v, int k) {
		used[v] = 1;
		cmp[v] = k;
		for (auto a : rG[v])if (used[a])rdfs(a, k);
	}
public:
	SCC(int size) :V(size + 1), G(size + 1), rG(size + 1), vs(size + 1), used(size + 1), cmp(size + 1) {}
	void add_edge(int from, int to) {
		solved = -1;
		G[from].push_back(to);
		rG[to].push_back(from);
	}
	int scc() {
		if (solved != -1)return solved;
		fill(ALL(used), 0);
		vs.clear();
		for (int i = 0; i < V; i++)if (!used[i])dfs(i);
		fill(ALL(used), 0);
		int k = 0;
		for (int i = vs.size() - 1; i >= 0; i--)if (!used[vs[i]])rdfs(vs[i], k++);
		solved = k;
		return k;
	}
	const auto& group() {
		return cmp;
	}
};
umap<pair<int, int>, int> m;
int f(int a, int b) {
	b &= (2ll << a - 1);
	if (m.find(pii(a, b)) != m.end())return m[pii(a, b)];
	set<int> s;
	rep1(i, a) {
		if (b & 1 << i)continue;
		s.insert(f(a - i, b | 1 << i));
	}
	rep(i, 60) {
		if (s.find(i) == s.end()) {
			m[pii(a, b)] = i;
			return i;
		}
	}
}
template<class T>
class lazysegtree {
	vector<T> obj;
	int offset;
	T e;
	int bufsize(int num) {
		int i = 1;
		for (; num >i; i <<= 1);
		offset = i - 1;
		return (i << 1) - 1;
	}
	T query(int a, int b, int k, int l, int r) {
		if (r <= a || b <= l)return e;
		if (a <= l && r <= b)return obj[k];
		else {
			T ret(e);
			obj[k].propagate(obj[k * 2 + 1], obj[k * 2 + 2]);
			return ret.merge(query(a, b, k * 2 + 1, l, (l + r) / 2), query(a, b, k * 2 + 2, (l + r) / 2, r));
		}
	}
	template<class Param>
	T update(int a, int b, int k, int l, int r, const Param& param) {
		if (r <= a || b <= l)return obj[k];
		if (a <= l && r <= b) {
			obj[k].update(param);
			return obj[k];
		}
		obj[k].propagate(obj[k * 2 + 1], obj[k * 2 + 2]);
		return obj[k].merge(update(a, b, k * 2 + 1, l, (l + r) / 2, param), update(a, b, k * 2 + 2, (l + r) / 2, r, param));
	}
public:
	T query(int a, int b) {//[a,b)
		return query(a, b, 0, 0, offset + 1);
	}
	template<class Param>
	void update(int a, int b, Param&& param) {
		update(a, b, 0, 0, offset + 1, param);
	}
	void updateall(int l = 0, int r = -1) {
		if (r < 0)r = offset + 1;
		l += offset, r += offset;
		if (l == 0)return;
		do {
			l = l - 1 >> 1, r = r - 1 >> 1;
			for (int i = l; i < r; i++)obj[i].merge(obj[i * 2 + 1], obj[i * 2 + 2]);
		} while (l);
	}
	/*
	void update(int k, T &a) {
	k += offset;
	obj[k] = a;
	while (k) {
	k = k - 1 >> 1;
	obj[k] = updater(obj[k * 2 + 1], obj[k * 2 + 2]);
	}
	}*/
	lazysegtree(int n, T e) :obj(bufsize(n), e), e(e) {}
	lazysegtree(vector<T> &vec, T e) :obj(bufsize(vec.size()), e), e(e) {
		copy(vec.begin(), vec.end(), obj.begin() + offset);
		updateall();
	}
	T& operator[](int n) {
		return obj[n + offset];
	}
};
class lazyRMQ_t {
	int min, add;
public:
	int getmin() {
		return min;
	}
	lazyRMQ_t() {
		min = numeric_limits<int>::max()/2; add = 0;
	}
	lazyRMQ_t(int a,int b=0) {
		min = a; add = b;
	}
	void propagate(lazyRMQ_t &a, lazyRMQ_t &b) {
		a.min += add;
		b.min += add;
		a.add += add;
		b.add += add;
		add = 0;
	}
	lazyRMQ_t& merge(const lazyRMQ_t &a,const lazyRMQ_t &b) {
		min = std::min(a.min, b.min);
		add = 0;
		return *this;
	}
	lazyRMQ_t& update(int k) {
		min += k;
		add += k;
		return *this;
	}
};
int dp[201][201];
int main() {
	int n;
	cin >> n;
	vector<char> c(n);
	rep(i, n)cin >> c[i];
	dp[0][0] = 1;
	rep(i, n){
		rep(j, n) {
			switch (c[i]) {
			case '-':
				(dp[i + 1][j] += dp[i][j]) %= mod;
				break;
			case 'U':
				(dp[i + 1][j] += (ll)dp[i][j] * j%mod) %= mod;
				(dp[i + 1][j + 1] += dp[i][j]) %= mod;
				break;
			case 'D':
				(dp[i + 1][j] += (ll)dp[i][j] * j%mod) %= mod;
				if (j == 0)break;
				(dp[i + 1][j - 1] += (ll)dp[i][j] * j*j%mod) %= mod;
			}
		}
	}
	cout << dp[n][0] << endl;
}

Measured memory_bytes: 3184