Util Prefix

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
#define pb push_back
#define all(X) (X).begin(), (X).end()
#define sz(X) (int)(X).size()
#define fi first
#define se second
#define lbi(X, n) int(lower_bound(all(X), n) - begin(X))
#define ubi(X, n) int(upper_bound(all(X), n) - begin(X))
#define maxa(X, Y) (X)=max((X),(Y))
#define mina(X, Y) (X)=min((X),(Y))
#define maxi(X) max_element(all(X)) - begin(X)
#define maxe(X) *max_element(all(X))
#define mini(X) min_element(all(X)) - begin(X)
#define mine(X) *min_element(all(X))
#define acc(X) accumulate(all(X), 0LL)
#define cntt(X, x) count(all(X),x)
#define mp(a, b) make_pair((a),(b))
#define has(X, x) (find(all((X)),x)!=(X).end())
#define hass(X, x) ((X).find(x) != (X).end())
#define hasstr(X, x) (!!strstr(&(X)[0],&(x)[0]))
#define uniq(X) sort(all(X)),(X).resize(unique(all((X))) - (X).begin())
const int MOD = 1e9 + 7;
inline ll md(ll x) { return x >= 0 && x < MOD ? x : (x %= MOD) < 0 ? x + MOD : x; }
#define mds(X, Y) ((X) = md((X) + (Y)))
#define mdm(X, Y) ((X) = md(1LL * (X) * (Y)))