結果
| 問題 | No.1354 Sambo's Treasure |
| ユーザー |
 PCTprobability
|
| 提出日時 | 2021-01-17 01:01:33 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 206 ms / 2,000 ms |
| コード長 | 41,482 bytes |
| コンパイル時間 | 4,457 ms |
| コンパイル使用メモリ | 269,956 KB |
| 実行使用メモリ | 85,504 KB |
| 最終ジャッジ日時 | 2024-05-09 13:53:20 |
| 合計ジャッジ時間 | 16,621 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 131 ms
73,752 KB |
| testcase_01 | AC | 133 ms
73,856 KB |
| testcase_02 | AC | 140 ms
73,832 KB |
| testcase_03 | AC | 147 ms
73,824 KB |
| testcase_04 | AC | 135 ms
73,708 KB |
| testcase_05 | AC | 143 ms
73,856 KB |
| testcase_06 | AC | 139 ms
73,824 KB |
| testcase_07 | AC | 140 ms
73,768 KB |
| testcase_08 | AC | 136 ms
73,728 KB |
| testcase_09 | AC | 149 ms
73,856 KB |
| testcase_10 | AC | 146 ms
73,856 KB |
| testcase_11 | AC | 138 ms
73,856 KB |
| testcase_12 | AC | 136 ms
73,748 KB |
| testcase_13 | AC | 131 ms
73,728 KB |
| testcase_14 | AC | 162 ms
73,728 KB |
| testcase_15 | AC | 136 ms
73,856 KB |
| testcase_16 | AC | 136 ms
73,804 KB |
| testcase_17 | AC | 140 ms
73,728 KB |
| testcase_18 | AC | 143 ms
73,856 KB |
| testcase_19 | AC | 141 ms
73,856 KB |
| testcase_20 | AC | 140 ms
73,820 KB |
| testcase_21 | AC | 128 ms
73,728 KB |
| testcase_22 | AC | 142 ms
73,820 KB |
| testcase_23 | AC | 184 ms
85,248 KB |
| testcase_24 | AC | 201 ms
85,248 KB |
| testcase_25 | AC | 182 ms
85,368 KB |
| testcase_26 | AC | 179 ms
85,248 KB |
| testcase_27 | AC | 188 ms
85,248 KB |
| testcase_28 | AC | 176 ms
85,248 KB |
| testcase_29 | AC | 189 ms
85,376 KB |
| testcase_30 | AC | 193 ms
85,248 KB |
| testcase_31 | AC | 189 ms
85,248 KB |
| testcase_32 | AC | 197 ms
85,248 KB |
| testcase_33 | AC | 182 ms
85,452 KB |
| testcase_34 | AC | 206 ms
85,324 KB |
| testcase_35 | AC | 189 ms
85,504 KB |
| testcase_36 | AC | 192 ms
85,248 KB |
| testcase_37 | AC | 197 ms
85,376 KB |
| testcase_38 | AC | 202 ms
85,248 KB |
| testcase_39 | AC | 182 ms
85,248 KB |
| testcase_40 | AC | 193 ms
85,248 KB |
| testcase_41 | AC | 192 ms
85,248 KB |
| testcase_42 | AC | 192 ms
85,376 KB |
| testcase_43 | AC | 132 ms
73,884 KB |
| testcase_44 | AC | 142 ms
73,776 KB |
| testcase_45 | AC | 162 ms
73,856 KB |
| testcase_46 | AC | 150 ms
73,836 KB |
| testcase_47 | AC | 154 ms
73,856 KB |
| testcase_48 | AC | 139 ms
73,776 KB |
| testcase_49 | AC | 145 ms
73,728 KB |
| testcase_50 | AC | 142 ms
73,852 KB |
| testcase_51 | AC | 136 ms
73,856 KB |
| testcase_52 | AC | 145 ms
73,728 KB |
| testcase_53 | AC | 147 ms
73,936 KB |
| testcase_54 | AC | 156 ms
73,856 KB |
| testcase_55 | AC | 145 ms
73,856 KB |
| testcase_56 | AC | 138 ms
73,852 KB |
| testcase_57 | AC | 144 ms
73,856 KB |
| testcase_58 | AC | 137 ms
73,872 KB |
| testcase_59 | AC | 136 ms
73,728 KB |
| testcase_60 | AC | 137 ms
73,856 KB |
| testcase_61 | AC | 126 ms
73,856 KB |
| testcase_62 | AC | 140 ms
73,856 KB |
| testcase_63 | AC | 180 ms
85,504 KB |
ソースコード
////////////////////////////////////////////////////////////////////////////////
// Give me AC!!! //
////////////////////////////////////////////////////////////////////////////////
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using ll = long long;
using ld = long double;
using graph = vector<vector<int>>;
#define NDEBUG
using int64 = long long;
const int64 infll = (1LL << 62) - 1;
#define all(s) (s).begin(),(s).end()
#define sz(x) (int) (x).size()
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define bit(n,k) ((n>>k)&1) /*nのk bit目*/
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
#define PQ priority_queue<vector<ll>,vector<vector<ll>>,greater<vector<ll>>>
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define S second //pairの二つ目の要素
#define coutY cout<<"YES"<<endl
#define couty cout<<"Yes"<<endl
#define coutN cout<<"NO"<<endl
#define coutn cout<<"No"<<endl
#define coutdouble(a,b) cout << fixed << setprecision(a) << double(b) ;
#define vi(a,b) vector<int> a(b)
#define vl(a,b) vector<ll> a(b)
#define vs(a,b) vector<string> a(b)
#define vll(a,b,c) vector<vector<ll>> a(b, vector<ll>(c));
#define intque(a) queue<int> a;
#define llque(a) queue<ll> a;
#define intque2(a) priority_queue<int, vector<int>, greater<int>> a;
#define llque2(a) priority_queue<ll, vector<ll>, greater<ll>> a;
#define pushback(a,b) a.push_back(b)
#define mapii(M1) map<int, int> M1;
#define cou(v,x) count(v.begin(), v.end(), x)
#define mapll(M1) map<ll,ll> M1;
#define mapls(M1) map<ll, string> M1;
#define mapsl(M1) map<string, ll> M1;
#define twolook(a,l,r,x) lower_bound(a+l, a+r, x) - a
#define sor(a) sort(a.begin(), a.end())
#define rever(a) reverse(a.begin(),a.end())
#define rep(i,a) for(ll i=0;i<a;i++)
#define vcin(n) for(ll i=0;i<ll(n.size());i++) cin>>n[i]
#define vcout(n) for(ll i=0;i<ll(n.size());i++) cout<<n[i]
#define vcin2(n) rep(i,ll(n.size())) rep(j,ll(n.at(0).size())) cin>>n[i][j]
#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)
#define drep(i, n) drep2(i, n, 0)
const ll mod = 998244353;
const ll MOD = 998244353;
//const ll MOD=1000000007;
//const ll mod=1000000007;
constexpr ll MAX = 3000000;
//const ll _max = 9223372036854775807;
const ll _max = 1223372036854775807;
const ll inf = 2000000000000000000ll;
static const long double pi = 3.141592653589793;
const int MAX_COL=350;
const int MAX_ROW=350;
ll fac[MAX],finv[MAX],inv[MAX];
typedef int FLOW; // フローを表す型、今回は int 型
const int MAX_V = 6000; // グラフの最大ノード数
const FLOW INF = 100000000;
// テーブルを作る前処理
void COMinit() {
fac[0] = fac[1] = 1;
finv[0] = finv[1] = 1;
inv[1] = 1;
for (int i = 2; i < MAX; i++){
fac[i] = fac[i - 1] * i % MOD;
inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
finv[i] = finv[i - 1] * inv[i] % MOD;
}
}
// 二項係数計算
long long COM(int n, int k){
if (n < k) return 0;
if (n < 0 || k < 0) return 0;
return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
ll HOM(ll n,ll k){
if(n+k-1>=n-1&&n-1>=0){
return COM(n+k-1,n-1);
}
else{
return 0;
}
}
ll modPow(long long a, long long n, long long p) {
if (a == 0 && n == 0) return 1;
if (n == 0) return 1; // 0乗にも対応する場合
if (n == 1) return a % p;
if (n % 2 == 1) return (a * modPow(a, n - 1, p)) % p;
long long t = modPow(a, n / 2, p);
return (t * t) % p;
}
ll clocks(ll a,ll b,ll c){
return a*3600+b*60+c;
}
ll divup(ll b,ll d){
if(b%d==0){
return b/d;
}
else{
return b/d+1;
}
}
ll zero(ll a){
return max(ll(0),a);
}
//aはbの何乗以下かを満たす数の内最大の物,(a,10)はaの桁数
ll expless(ll a,ll b){
ll k=0;
ll o=1;
while(a>=o){
k++;
o=o*b;
}
return k;
}
//aをb進法で表す
//b進法のaを10進法に直す
ll tenbase(ll a,ll b){
ll c=expless(a,10);
ll ans=0;
ll k=1;
for(int i=0;i<c;i++){
ans+=(a%10)*k;
k=k*b;
a=a/10;
}
return ans;
}
vector<pair<long long, long long> > prime_factorize(long long N) {
vector<pair<long long, long long> > res;
for (long long a = 2; a * a <= N; ++a) {
if (N % a != 0) continue;
long long ex = 0; // 指数
// 割れる限り割り続ける
while (N % a == 0) {
++ex;
N /= a;
}
// その結果を push
res.push_back({a, ex});
}
// 最後に残った数について
if (N != 1) res.push_back({N, 1});
return res;
}
template <class T, class U>
void chmin(T& t, const U& u) {
if (t > u) t = u;
}
template <class T, class U>
void chmax(T& t, const U& u) {
if (t < u) t = u;
}
//aがbで何回割り切るか
ll exp(ll a,ll b){
ll ans=0;
while(a%b==0){
a=a/b;
ans++;
}
return ans;
}
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int X[6]={1,1,0,-1,-1,0};
const int Y[6]={0,1,1,0,-1,-1};
template<typename T>
vector<T> smallest_prime_factors(T n) {
vector<T> spf(n + 1);
for (int i = 0; i <= n; i++) spf[i] = i;
for (T i = 2; i * i <= n; i++) {
// 素数だったら
if (spf[i] == i) {
for (T j = i * i; j <= n; j += i) {
// iを持つ整数かつまだ素数が決まっていないなら
if (spf[j] == j) {
spf[j] = i;
}
}
}
}
return spf;
}
vector<pair<ll,ll>> factolization(ll x, vector<ll> &spf) {
vector<pair<ll,ll>> ret;
ll p;
ll z;
while (x != 1) {
p=(spf[x]);
z=0;
while(x%p==0){
z++;
x /= p;
}
ret.push_back({p, z});
}
return ret;
}
vector<bool> is;
vector<long long int> prime_(ll n){
is.resize(n+1, true);
is[0] = false;
is[1] = false;
vector<long long int> primes;
for (int i=2; i<=n; i++) {
if (is[i] == true){
primes.push_back(i);
for (int j=i*2; j<=n; j+=i){
is[j] = false;
}
}
}
return primes;
}
ll so(ll a){
ll ans=0;
if(a==0){
return 0;
}
while(a%2==0){
a/=2;
ans++;
}
return ans;
}
ll binary(ll bina){
ll ans = 0;
for (ll i = 0; bina>0 ; i++)
{
ans = ans+(bina%2)*pow(10,i);
bina = bina/2;
}
return ans;
}
vector<long long> enum_divisors(long long N) {
vector<long long> res;
for (long long i = 1; i * i <= N; ++i) {
if (N % i == 0) {
res.push_back(i);
// 重複しないならば i の相方である N/i も push
if (N/i != i) res.push_back(N/i);
}
}
// 小さい順に並び替える
sort(res.begin(), res.end());
return res;
}
ll vectorcheck(vector<ll> t,ll key){
auto iter = lower_bound(ALL(t), key);
auto iter2 = upper_bound(ALL(t), key);
if((iter-t.begin())!=(iter2-t.begin())){
return 1;
}
else{
return 0;
}
}
int ctoi(const char c){
switch(c){
case '0': return 0;
case '1': return 1;
case '2': return 2;
case '3': return 3;
case '4': return 4;
case '5': return 5;
case '6': return 6;
case '7': return 7;
case '8': return 8;
case '9': return 9;
default : return -1;
}
}
ll ord(ll a,ll b){
ll ans=0;
while(a%b==0){
ans++;
a/=b;
}
return ans;
}
ll atll(ll a,ll b){
b++;
ll c=expless(a,10);
ll d=c-b;
ll f=1;
for(int i=0;i<d;i++){
f=f*10;
}
a=(a/f);
return a%10;
}
struct BitMatrix {
int H, W;
bitset<MAX_COL> val[MAX_ROW];
BitMatrix(int m = 1, int n = 1) : H(m), W(n) {}
inline bitset<MAX_COL>& operator [] (int i) {return val[i];}
};
int GaussJordan(BitMatrix &A, bool is_extended = false) {
int rank = 0;
for (int col = 0; col < A.W; ++col) {
if (is_extended && col == A.W - 1) break;
int pivot = -1;
for (int row = rank; row < A.H; ++row) {
if (A[row][col]) {
pivot = row;
break;
}
}
if (pivot == -1) continue;
swap(A[pivot], A[rank]);
for (int row = 0; row < A.H; ++row) {
if (row != rank && A[row][col]) A[row] ^= A[rank];
}
++rank;
}
return rank;
}
int pos(const char c){
if('a' <= c && c <= 'z') return (c-'a');
return -1;
}
// グラフの辺の構造体
struct Edge {
int rev, from, to;
FLOW cap, icap;
Edge(int r, int f, int t, FLOW c) : rev(r), from(f), to(t), cap(c), icap(c) {}
friend ostream& operator << (ostream& s, const Edge& E) {
if (E.cap > 0) return s << E.from << "->" << E.to << '(' << E.cap << ')';
else return s;
}
};
// グラフ構造体
struct Graph {
int V;
vector<Edge> list[MAX_V];
Graph(int n = 0) : V(n) { for (int i = 0; i < MAX_V; ++i) list[i].clear(); }
void init(int n = 0) { V = n; for (int i = 0; i < MAX_V; ++i) list[i].clear(); }
void resize(int n = 0) { V = n; }
void reset() { for (int i = 0; i < V; ++i) for (int j = 0; j < int(list[i].size()); ++j) list[i][j].cap = list[i][j].icap; }
inline vector<Edge>& operator [] (int i) { return list[i]; }
Edge &redge(Edge e) {
if (e.from != e.to) return list[e.to][e.rev];
else return list[e.to][e.rev + 1];
}
void addedge(int from, int to, FLOW cap) {
list[from].push_back(Edge((int)list[to].size(), from, to, cap));
list[to].push_back(Edge((int)list[from].size() - 1, to, from, 0));
}
};
// 最大流を求めるサブルーチンたち
static int level[MAX_V];
static int iter[MAX_V];
void dibfs(Graph &G, int s) {
for (int i = 0; i < MAX_V; ++i) level[i] = -1;
level[s] = 0;
queue<int> que;
que.push(s);
while (!que.empty()) {
int v = que.front();
que.pop();
for (int i = 0; i < int(G[v].size()); ++i) {
Edge &e = G[v][i];
if (level[e.to] < 0 && e.cap > 0) {
level[e.to] = level[v] + 1;
que.push(e.to);
}
}
}
}
FLOW didfs(Graph &G, int v, int t, FLOW f) {
if (v == t) return f;
for (int &i = iter[v]; i < int(G[v].size()); ++i) {
Edge &e = G[v][i], &re = G.redge(e);
if (level[v] < level[e.to] && e.cap > 0) {
FLOW d = didfs(G, e.to, t, min(f, e.cap));
if (d > 0) {
e.cap -= d;
re.cap += d;
return d;
}
}
}
return 0;
}
// 最大流を求めるメイン関数
FLOW Dinic(Graph &G, int s, int t) {
FLOW res = 0;
while (true) {
dibfs(G, s);
if (level[t] < 0) return res;
memset(iter, 0, sizeof(iter));
FLOW flow;
while ((flow = didfs(G, s, t, INF)) > 0) {
res += flow;
}
}
}
vector<ll> topological_sort(vector<vector<ll>> &G, vector<ll> &indegree, ll V) {
// トポロジカルソートを記録する配列
vector<ll> sorted_vertices;
// 入次数が0の頂点を発見したら、処理待ち頂点としてキューに追加する
queue<ll> que;
for (int i = 0; i < V; i++) {
if (indegree[i] == 0) {
que.push(i);
}
}
// キューが空になるまで、操作1~3を繰り返す
while (que.empty() == false) {
// キューの先頭の頂点を取り出す
int v = que.front();
que.pop();
// その頂点と隣接している頂点の入次数を減らし、0になればキューに追加
for (int i = 0; i < int(G[v].size()); i++) {
int u = G[v][i];
indegree[u] -= 1;
if (indegree[u] == 0) que.push(u);
}
// 頂点vを配列の末尾に追加する
sorted_vertices.push_back(v);
}
// トポロジカルソートを返す
return sorted_vertices;
}
vector<vector<ll>> multi(vector<vector<ll>> a, vector<vector<ll>> b){
ll n = a.size();
vector<vector<ll>> res(n, vector<ll>(n, 0));
for (ll i = 0; i < n; ++i){
for (ll j = 0; j < n; ++j){
for (ll x = 0; x < n; ++x){
res[i][j] = (res[i][j] + (a[i][x] * b[x][j])) % mod;
}
}
}
return res;
}
vector<vector<ll>> mul_exp(vector<vector<ll>> adj, ll k, ll n){
if (k == 1) return adj;
vector<vector<ll>> res = mul_exp(adj, k / 2, n);
if (k % 2 == 0) return multi(res, res);
else return multi(adj, multi(res, res));
}
struct CHT {
struct Line {
ll slope, yIntercept;
Line(ll slope, ll yIntercept) : slope(slope), yIntercept(yIntercept) {}
ll val(ll x) {
return slope * x + yIntercept;
}
ll intersect(Line y) {
return (y.yIntercept - yIntercept + slope - y.slope - 1) / (slope - y.slope);
}
};
deque<pair<Line, ll>> dq;
void insert(ll slope, ll yIntercept) {
Line newLine(slope, yIntercept);
while (sz(dq) > 1 && dq.back().second >= dq.back().first.intersect(newLine))
dq.pop_back();
if (dq.empty()) {
dq.emplace_back(newLine, 0);
return;
}
dq.emplace_back(newLine, dq.back().first.intersect(newLine));
}
ll query(ll x) {
while (sz(dq) > 1) {
if (dq[1].second <= x) dq.pop_front();
else break;
}
return dq[0].first.val(x);
}
ll query2(ll x) {
auto qry = *lower_bound(dq.rbegin(), dq.rend(),
make_pair(Line(0, 0), x),
[&](const pair<Line, int> &a, const pair<Line, int> &b) {
return a.second > b.second;
});
return qry.first.val(x);
}
};
template <typename T>
int compress(vector<T> x, map<T, int> &zip, vector<int> &unzip) {
sort(x.begin(), x.end());
x.erase(unique(x.begin(), x.end()), x.end());
for (int i = 0; i < x.size(); i++) {
zip[x[i]] = i;
unzip[i] = x[i];
}
return x.size();
}
long long modlog(long long x,long long y,long long MOD){
x %= MOD;
y %= MOD;
long long H = sqrt(MOD);
vector<pair<long long,long long>> baby(H);
// Baby-step
long long Z = y;
for(long long a=0;a<H;a++){ //yx^(H-1)
baby[a] = make_pair(Z,a);
Z = (Z*x) % MOD;
}
sort(baby.begin(),baby.end());
// Giant step
long long xH=1;
for(int i=0;i<H;i++) xH = (xH*x) % MOD;
long long xaH = 1;
for(int a=1;a<=(MOD/H)+1;a++){
xaH = (xaH*xH) % MOD;
auto itr = lower_bound(baby.begin(),baby.end(),make_pair(xaH+1,0LL));
if(itr->second==H) continue;
itr--;
if(itr->first==xaH) return a*H - itr->second;
}
return -1;
}
vector<pair<ll,ll>> lp(vector<ll> a){
sor(a);
ll x=a.at(0);
ll y=1;
vector<pair<ll,ll>> ans;
for(int i=1;i<int(a.size());i++){
if(a.at(i)!=a.at(i-1)){
ans.push_back({x,y});
x=a.at(i);
y=1;
}
else{
y++;
}
}
if(y!=0){
ans.push_back({x,y});
}
return ans;
}
typedef unsigned long long ull;
#define B1 100000007
#define B2 1000000007
bool rolling_hash(string const& S, int t_start, int m){
int s_start = t_start + m;
// B^mを用意する
ull pow_B_m_1 = 1, pow_B_m_2 = 1;
for(int k = 0; k < m; k++){
pow_B_m_1 *= B1, pow_B_m_2 *= B2;
}
// sとtの先頭m文字のハッシュ値sh,thを計算
ull sh1 = 0, sh2 = 0, th1 = 0, th2 = 0;
for(int k = 0; k < m; k++){
th1 = th1 * B1 + S[t_start + k], th2 = th2 * B2 + S[t_start + k];
sh1 = sh1 * B1 + S[s_start + k], sh2 = sh2 * B2 + S[s_start + k];
}
// sをずらしてハッシュ値を更新
for(int k = 0; s_start + k < int(S.length()); k++){
if(sh1 == th1 && sh2 == th2) return true;
if(k + s_start < int(S.length())){
sh1 = sh1 * B1 + S[s_start + m + k] - S[s_start + k] * pow_B_m_1;
sh2 = sh2 * B2 + S[s_start + m + k] - S[s_start + k] * pow_B_m_2;
}
}
return false;
}
constexpr double PI = acosl(-1);
struct Comp {
double real, imag;
Comp(double real = 0, double imag = 0) : real(real), imag(imag) {}
friend inline ostream& operator << (ostream &s, const Comp &c) {
return s << '<' << c.real << ',' << c.imag << '>';
}
inline Comp operator + (const Comp &c) {
return {real + c.real, imag + c.imag};
}
inline Comp operator - (const Comp &c) {
return {real - c.real, imag - c.imag};
}
inline Comp operator * (const Comp &c) {
return {real * c.real - imag * c.imag,
real * c.imag + imag * c.real};
}
inline Comp operator * (double a) {
return {real * a, imag * a};
}
inline Comp operator / (double a) {
return {real / a, imag / a};
}
};
// FFT
void trans(vector<Comp> &v, bool inv = false) {
int n = SIZE(v);
for (int i = 0, j = 1; j < n-1; j++) {
for (int k = n>>1; k > (i ^= k); k >>= 1);
if (i > j) swap(v[i], v[j]);
}
for (int t = 2; t <= n; t <<= 1) {
double ang = acosl(-1.0) * 2 / t;
if (inv) ang = -ang;
for (int i = 0; i < n; i += t) {
REP(j, t/2) {
Comp w = {cos(ang * j), sin(ang * j)};
int j1 = i + j, j2 = i + j + t/2;
Comp c1 = v[j1], c2 = v[j2] * w;
v[j1] = c1 + c2;
v[j2] = c1 - c2;
}
}
}
if (inv) REP(i, n) v[i] = v[i]/n;
}
// A * B
vector<ll> mult(const vector<ll> &A,
const vector<ll> &B) {
int size_a = 1; while (size_a < SIZE(A)) size_a <<= 1;
int size_b = 1; while (size_b < SIZE(B)) size_b <<= 1;
int size_fft = max(size_a, size_b) << 1;
vector<Comp> cA(size_fft), cB(size_fft), cC(size_fft);
for (int i = 0; i < SIZE(A); ++i) cA[i] = {(double)A[i], 0};
for (int i = 0; i < SIZE(B); ++i) cB[i] = {(double)B[i], 0};
trans(cA); trans(cB);
REP(i, size_fft) cC[i] = cA[i] * cB[i];
trans(cC, true);
vector<ll> res(SIZE(A) + SIZE(B) - 1);
for (int i = 0; i < SIZE(res); ++i) {
res[i] = (ll)(cC[i].real + 0.5);
}
return res;
}
template<typename T>
struct BellmanFord {
struct Vertex {
int to; T cost;
Vertex (int to_, T cost_) : to(to_), cost(cost_) {}
};
T INF;
const int n;
vector<vector<Vertex>> Graph, invGraph;
vector<T> dt;
vector<bool> reach;
void reachable(const int now, vector<bool> &seen){
if(seen[now]) return;
seen[now] = true;
for(const Vertex nxt : Graph[now]) reachable(nxt.to, seen);
}
public:
bool loop = false;
BellmanFord (const int n_, const T INF_ = numeric_limits<T>::max()/2)
: INF(INF_), n(n_), Graph(n_), invGraph(n_), dt(n, INF), reach(n, true) {}
T operator [] (const int i) { return dt[i]; }
void AddEdge(const int from, const int to, const T cost){
Graph[from].push_back(Vertex(to, cost));
}
void Build (const int from){
dt[from] = 0;
for(int i = 0; i < n; i++){
bool update = false;
for(int now = 0; now < n; now++){
if(!reach[now]) continue;
for(const Vertex nxt : Graph[now]){
if(!reach[nxt.to] or dt[now] == INF) continue;
if(dt[nxt.to] > dt[now] + nxt.cost){
dt[nxt.to] = dt[now] + nxt.cost;
update = true;
if(i == n-1) loop = true;
}
}
}
if(!update) break;
}
}
void Build (const int from, const int to){
for(int i = 0; i < n; i++){
vector<bool> seen(n, false);
reachable(i, seen);
reach[i] = seen[to];
}
Build(from);
}
};
ll P(ll a,ll b){
if(a<0||b<0||a<b) return -1;
ll c=a-b;
c=modPow(fac[c],mod-2,mod);
a=fac[a];
a*=c;
a%=mod;
return a;
}
class UnionFind {
public:
vector <ll> par; // 各元の親を表す配列
vector <ll> siz; // 素集合のサイズを表す配列(1 で初期化)
// Constructor
UnionFind(ll sz_): par(sz_), siz(sz_, 1LL) {
for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
}
void init(ll sz_) {
par.resize(sz_);
siz.assign(sz_, 1LL); // resize だとなぜか初期化されなかった
for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
}
// Member Function
// Find
ll root(ll x) { // 根の検索
while (par[x] != x) {
x = par[x] = par[par[x]]; // x の親の親を x の親とする
}
return x;
}
// Union(Unite, Merge)
bool merge(ll x, ll y) {
x = root(x);
y = root(y);
if (x == y) return false;
// merge technique（データ構造をマージするテク．小を大にくっつける）
if (siz[x] < siz[y]) swap(x, y);
siz[x] += siz[y];
par[y] = x;
return true;
}
bool issame(ll x, ll y) { // 連結判定
return root(x) == root(y);
}
ll size(ll x) { // 素集合のサイズ
return siz[root(x)];
}
};
template<class Monoid, class Action> struct SegTree {
using FuncMonoid = function< Monoid(Monoid, Monoid) >;
using FuncAction = function< void(Monoid&, Action) >;
using FuncLazy = function< void(Action&, Action) >;
FuncMonoid FM;
FuncAction FA;
FuncLazy FL;
Monoid IDENTITY_MONOID;
Action IDENTITY_LAZY;
int SIZE, HEIGHT;
vector<Monoid> dat;
vector<Action> lazy;
SegTree() { }
SegTree(int n, const FuncMonoid fm, const FuncAction fa, const FuncLazy fl,
const Monoid &identity_monoid, const Action &identity_lazy)
: FM(fm), FA(fa), FL(fl),
IDENTITY_MONOID(identity_monoid), IDENTITY_LAZY(identity_lazy) {
SIZE = 1, HEIGHT = 0;
while (SIZE < n) SIZE <<= 1, ++HEIGHT;
dat.assign(SIZE * 2, IDENTITY_MONOID);
lazy.assign(SIZE * 2, IDENTITY_LAZY);
}
void init(int n, const FuncMonoid fm, const FuncAction fa, const FuncLazy fl,
const Monoid &identity_monoid, const Action &identity_lazy) {
FM = fm, FA = fa, FL = fl;
IDENTITY_MONOID = identity_monoid, IDENTITY_LAZY = identity_lazy;
SIZE = 1; HEIGHT = 0;
while (SIZE < n) SIZE <<= 1, ++HEIGHT;
dat.assign(SIZE * 2, IDENTITY_MONOID);
lazy.assign(SIZE * 2, IDENTITY_LAZY);
}
// set, a is 0-indexed
void set(int a, const Monoid &v) { dat[a + SIZE] = v; }
void build() {
for (int k = SIZE - 1; k > 0; --k)
dat[k] = FM(dat[k*2], dat[k*2+1]);
}
// update [a, b)
inline void evaluate(int k) {
if (lazy[k] == IDENTITY_LAZY) return;
if (k < SIZE) FL(lazy[k*2], lazy[k]), FL(lazy[k*2+1], lazy[k]);
FA(dat[k], lazy[k]);
lazy[k] = IDENTITY_LAZY;
}
inline void update(int a, int b, const Action &v, int k, int l, int r) {
evaluate(k);
if (a <= l && r <= b) FL(lazy[k], v), evaluate(k);
else if (a < r && l < b) {
update(a, b, v, k*2, l, (l+r)>>1);
update(a, b, v, k*2+1, (l+r)>>1, r);
dat[k] = FM(dat[k*2], dat[k*2+1]);
}
}
inline void update(int a, int b, const Action &v) {
update(a, b, v, 1, 0, SIZE);
}
// get [a, b)
inline Monoid get(int a, int b, int k, int l, int r) {
evaluate(k);
if (a <= l && r <= b)
return dat[k];
else if (a < r && l < b)
return FM(get(a, b, k*2, l, (l+r)>>1),
get(a, b, k*2+1, (l+r)>>1, r));
else
return IDENTITY_MONOID;
}
inline Monoid get(int a, int b) {
return get(a, b, 1, 0, SIZE);
}
inline Monoid operator [] (int a) {
return get(a, a + 1);
}
// debug
void print() {
for (int i = 0; i < SIZE; ++i) {
if (i) cout << ",";
cout << (*this)[i];
}
cout << endl;
}
};
template< typename T >
struct FormalPowerSeries : vector< T > {
using vector< T >::vector;
using P = FormalPowerSeries;
using MULT = function< P(P, P) >;
using FFT = function< void(P &) >;
using SQRT = function< T(T) >;
static MULT &get_mult() {
static MULT mult = nullptr;
return mult;
}
static void set_mult(MULT f) {
get_mult() = f;
}
static FFT &get_fft() {
static FFT fft = nullptr;
return fft;
}
static FFT &get_ifft() {
static FFT ifft = nullptr;
return ifft;
}
static void set_fft(FFT f, FFT g) {
get_fft() = f;
get_ifft() = g;
}
static SQRT &get_sqrt() {
static SQRT sqr = nullptr;
return sqr;
}
static void set_sqrt(SQRT sqr) {
get_sqrt() = sqr;
}
void shrink() {
while(this->size() && this->back() == T(0)) this->pop_back();
}
P operator+(const P &r) const { return P(*this) += r; }
P operator+(const T &v) const { return P(*this) += v; }
P operator-(const P &r) const { return P(*this) -= r; }
P operator-(const T &v) const { return P(*this) -= v; }
P operator*(const P &r) const { return P(*this) *= r; }
P operator*(const T &v) const { return P(*this) *= v; }
P operator/(const P &r) const { return P(*this) /= r; }
P operator%(const P &r) const { return P(*this) %= r; }
P &operator+=(const P &r) {
if(r.size() > this->size()) this->resize(r.size());
for(int i = 0; i < r.size(); i++) (*this)[i] += r[i];
return *this;
}
P &operator+=(const T &r) {
if(this->empty()) this->resize(1);
(*this)[0] += r;
return *this;
}
P &operator-=(const P &r) {
if(r.size() > this->size()) this->resize(r.size());
for(int i = 0; i < r.size(); i++) (*this)[i] -= r[i];
shrink();
return *this;
}
P &operator-=(const T &r) {
if(this->empty()) this->resize(1);
(*this)[0] -= r;
shrink();
return *this;
}
P &operator*=(const T &v) {
const int n = (int) this->size();
for(int k = 0; k < n; k++) (*this)[k] *= v;
return *this;
}
P &operator*=(const P &r) {
if(this->empty() || r.empty()) {
this->clear();
return *this;
}
assert(get_mult() != nullptr);
return *this = get_mult()(*this, r);
}
P &operator%=(const P &r) { return *this -= *this / r * r; }
P operator-() const {
P ret(this->size());
for(int i = 0; i < this->size(); i++) ret[i] = -(*this)[i];
return ret;
}
P &operator/=(const P &r) {
if(this->size() < r.size()) {
this->clear();
return *this;
}
int n = this->size() - r.size() + 1;
return *this = (rev().pre(n) * r.rev().inv(n)).pre(n).rev(n);
}
P dot(P r) const {
P ret(min(this->size(), r.size()));
for(int i = 0; i < ret.size(); i++) ret[i] = (*this)[i] * r[i];
return ret;
}
P pre(int sz) const { return P(begin(*this), begin(*this) + min((int) this->size(), sz)); }
P operator>>(int sz) const {
if(this->size() <= sz) return {};
P ret(*this);
ret.erase(ret.begin(), ret.begin() + sz);
return ret;
}
P operator<<(int sz) const {
P ret(*this);
ret.insert(ret.begin(), sz, T(0));
return ret;
}
P rev(int deg = -1) const {
P ret(*this);
if(deg != -1) ret.resize(deg, T(0));
reverse(begin(ret), end(ret));
return ret;
}
P diff() const {
const int n = (int) this->size();
P ret(max(0, n - 1));
for(int i = 1; i < n; i++) ret[i - 1] = (*this)[i] * T(i);
return ret;
}
P integral() const {
const int n = (int) this->size();
P ret(n + 1);
ret[0] = T(0);
for(int i = 0; i < n; i++) ret[i + 1] = (*this)[i] / T(i + 1);
return ret;
}
// F(0) must not be 0
P inv(int deg = -1) const {
assert(((*this)[0]) != T(0));
const int n = (int) this->size();
if(deg == -1) deg = n;
if(get_fft() != nullptr) {
P ret(*this);
ret.resize(deg, T(0));
return ret.inv_fast();
}
P ret({T(1) / (*this)[0]});
for(int i = 1; i < deg; i <<= 1) {
ret = (ret + ret - ret * ret * pre(i << 1)).pre(i << 1);
}
return ret.pre(deg);
}
// F(0) must be 1
P log(int deg = -1) const {
assert((*this)[0] == 1);
const int n = (int) this->size();
if(deg == -1) deg = n;
return (this->diff() * this->inv(deg)).pre(deg - 1).integral();
}
P sqrt(int deg = -1) const {
const int n = (int) this->size();
if(deg == -1) deg = n;
if((*this)[0] == T(0)) {
for(int i = 1; i < n; i++) {
if((*this)[i] != T(0)) {
if(i & 1) return {};
if(deg - i / 2 <= 0) break;
auto ret = (*this >> i).sqrt(deg - i / 2);
if(ret.empty()) return {};
ret = ret << (i / 2);
if(ret.size() < deg) ret.resize(deg, T(0));
return ret;
}
}
return P(deg, 0);
}
P ret;
if(get_sqrt() == nullptr) {
assert((*this)[0] == T(1));
ret = {T(1)};
} else {
auto sqr = get_sqrt()((*this)[0]);
if(sqr * sqr != (*this)[0]) return {};
ret = {T(sqr)};
}
T inv2 = T(1) / T(2);
for(int i = 1; i < deg; i <<= 1) {
ret = (ret + pre(i << 1) * ret.inv(i << 1)) * inv2;
}
return ret.pre(deg);
}
// F(0) must be 0
P exp(int deg = -1) const {
assert((*this)[0] == T(0));
const int n = (int) this->size();
if(deg == -1) deg = n;
if(get_fft() != nullptr) {
P ret(*this);
ret.resize(deg, T(0));
return ret.exp_rec();
}
P ret({T(1)});
for(int i = 1; i < deg; i <<= 1) {
ret = (ret * (pre(i << 1) + T(1) - ret.log(i << 1))).pre(i << 1);
}
return ret.pre(deg);
}
P online_convolution_exp(const P &conv_coeff) const {
const int n = (int) conv_coeff.size();
assert((n & (n - 1)) == 0);
vector< P > conv_ntt_coeff;
for(int i = n; i >= 1; i >>= 1) {
P g(conv_coeff.pre(i));
get_fft()(g);
conv_ntt_coeff.emplace_back(g);
}
P conv_arg(n), conv_ret(n);
auto rec = [&](auto rec, int l, int r, int d) -> void {
if(r - l <= 16) {
for(int i = l; i < r; i++) {
T sum = 0;
for(int j = l; j < i; j++) sum += conv_arg[j] * conv_coeff[i - j];
conv_ret[i] += sum;
conv_arg[i] = i == 0 ? T(1) : conv_ret[i] / i;
}
} else {
int m = (l + r) / 2;
rec(rec, l, m, d + 1);
P pre(r - l);
for(int i = 0; i < m - l; i++) pre[i] = conv_arg[l + i];
get_fft()(pre);
for(int i = 0; i < r - l; i++) pre[i] *= conv_ntt_coeff[d][i];
get_ifft()(pre);
for(int i = 0; i < r - m; i++) conv_ret[m + i] += pre[m + i - l];
rec(rec, m, r, d + 1);
}
};
rec(rec, 0, n, 0);
return conv_arg;
}
P exp_rec() const {
assert((*this)[0] == T(0));
const int n = (int) this->size();
int m = 1;
while(m < n) m *= 2;
P conv_coeff(m);
for(int i = 1; i < n; i++) conv_coeff[i] = (*this)[i] * i;
return online_convolution_exp(conv_coeff).pre(n);
}
P inv_fast() const {
assert(((*this)[0]) != T(0));
const int n = (int) this->size();
P res{T(1) / (*this)[0]};
for(int d = 1; d < n; d <<= 1) {
P f(2 * d), g(2 * d);
for(int j = 0; j < min(n, 2 * d); j++) f[j] = (*this)[j];
for(int j = 0; j < d; j++) g[j] = res[j];
get_fft()(f);
get_fft()(g);
for(int j = 0; j < 2 * d; j++) f[j] *= g[j];
get_ifft()(f);
for(int j = 0; j < d; j++) {
f[j] = 0;
f[j + d] = -f[j + d];
}
get_fft()(f);
for(int j = 0; j < 2 * d; j++) f[j] *= g[j];
get_ifft()(f);
for(int j = 0; j < d; j++) f[j] = res[j];
res = f;
}
return res.pre(n);
}
P pow(int64_t k, int deg = -1) const {
const int n = (int) this->size();
if(deg == -1) deg = n;
for(int i = 0; i < n; i++) {
if((*this)[i] != T(0)) {
T rev = T(1) / (*this)[i];
P ret = (((*this * rev) >> i).log() * k).exp() * ((*this)[i].pow(k));
if(i * k > deg) return P(deg, T(0));
ret = (ret << (i * k)).pre(deg);
if(ret.size() < deg) ret.resize(deg, T(0));
return ret;
}
}
return *this;
}
T eval(T x) const {
T r = 0, w = 1;
for(auto &v : *this) {
r += w * v;
w *= x;
}
return r;
}
P pow_mod(int64_t n, P mod) const {
P modinv = mod.rev().inv();
auto get_div = [&](P base) {
if(base.size() < mod.size()) {
base.clear();
return base;
}
int n = base.size() - mod.size() + 1;
return (base.rev().pre(n) * modinv.pre(n)).pre(n).rev(n);
};
P x(*this), ret{1};
while(n > 0) {
if(n & 1) {
ret *= x;
ret -= get_div(ret) * mod;
}
x *= x;
x -= get_div(x) * mod;
n >>= 1;
}
return ret;
}
};
template< typename Mint >
struct NumberTheoreticTransformFriendlyModInt {
vector< int > rev;
vector< Mint > rts;
int base, max_base;
Mint root;
NumberTheoreticTransformFriendlyModInt() : base(1), rev{0, 1}, rts{0, 1} {
const int mod = Mint::get_mod();
assert(mod >= 3 && mod % 2 == 1);
auto tmp = mod - 1;
max_base = 0;
while(tmp % 2 == 0) tmp >>= 1, max_base++;
root = 2;
while(root.pow((mod - 1) >> 1) == 1) root += 1;
assert(root.pow(mod - 1) == 1);
root = root.pow((mod - 1) >> max_base);
}
void ensure_base(int nbase) {
if(nbase <= base)
return;
rev.resize(1 << nbase);
rts.resize(1 << nbase);
for(int i = 0; i < (1 << nbase); i++) {
rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (nbase - 1));
}
assert(nbase <= max_base);
while(base < nbase) {
Mint z = root.pow(1 << (max_base - 1 - base));
for(int i = 1 << (base - 1); i < (1 << base); i++) {
rts[i << 1] = rts[i];
rts[(i << 1) + 1] = rts[i] * z;
}
++base;
}
}
void ntt(vector< Mint > &a) {
const int n = (int) a.size();
assert((n & (n - 1)) == 0);
int zeros = __builtin_ctz(n);
ensure_base(zeros);
int shift = base - zeros;
for(int i = 0; i < n; i++) {
if(i < (rev[i] >> shift)) {
swap(a[i], a[rev[i] >> shift]);
}
}
for(int k = 1; k < n; k <<= 1) {
for(int i = 0; i < n; i += 2 * k) {
for(int j = 0; j < k; j++) {
Mint z = a[i + j + k] * rts[j + k];
a[i + j + k] = a[i + j] - z;
a[i + j] = a[i + j] + z;
}
}
}
}
void intt(vector< Mint > &a) {
const int n = (int) a.size();
ntt(a);
reverse(a.begin() + 1, a.end());
Mint inv_sz = Mint(1) / n;
for(int i = 0; i < n; i++) a[i] *= inv_sz;
}
vector< Mint > multiply(vector< Mint > a, vector< Mint > b) {
int need = a.size() + b.size() - 1;
int nbase = 1;
while((1 << nbase) < need) nbase++;
ensure_base(nbase);
int sz = 1 << nbase;
a.resize(sz, 0);
b.resize(sz, 0);
ntt(a);
ntt(b);
Mint inv_sz = Mint(1) / sz;
for(int i = 0; i < sz; i++) {
a[i] *= b[i] * inv_sz;
}
reverse(a.begin() + 1, a.end());
ntt(a);
a.resize(need);
return a;
}
};
template< int mod >
struct ModInt {
int x;
ModInt() : x(0) {}
ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
ModInt &operator+=(const ModInt &p) {
if((x += p.x) >= mod) x -= mod;
return *this;
}
ModInt &operator-=(const ModInt &p) {
if((x += mod - p.x) >= mod) x -= mod;
return *this;
}
ModInt &operator*=(const ModInt &p) {
x = (int) (1LL * x * p.x % mod);
return *this;
}
ModInt &operator/=(const ModInt &p) {
*this *= p.inverse();
return *this;
}
ModInt operator-() const { return ModInt(-x); }
ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
bool operator==(const ModInt &p) const { return x == p.x; }
bool operator!=(const ModInt &p) const { return x != p.x; }
ModInt inverse() const {
int a = x, b = mod, u = 1, v = 0, t;
while(b > 0) {
t = a / b;
swap(a -= t * b, b);
swap(u -= t * v, v);
}
return ModInt(u);
}
ModInt pow(int64_t n) const {
ModInt ret(1), mul(x);
while(n > 0) {
if(n & 1) ret *= mul;
mul *= mul;
n >>= 1;
}
return ret;
}
friend ostream &operator<<(ostream &os, const ModInt &p) {
return os << p.x;
}
friend istream &operator>>(istream &is, ModInt &a) {
int64_t t;
is >> t;
a = ModInt< mod >(t);
return (is);
}
static int get_mod() { return mod; }
};
using modint = ModInt< mod >;
template< typename T >
FormalPowerSeries< T > bernoulli(int N) {
FormalPowerSeries< T > poly(N + 1);
poly[0] = T(1);
for(int i = 1; i <= N; i++) {
poly[i] = poly[i - 1] / T(i + 1);
}
poly = poly.inv();
T tmp(1);
for(int i = 1; i <= N; i++) {
tmp *= T(i);
poly[i] *= tmp;
}
return poly;
}
vector<ll> grid(ll n,ll m,vector<pair<ll,ll>> g){
ll f=int(g.size());
f++;
g.push_back({n,m});
vector<ll> x(f);
vector<ll> y(f);
sor(g);
for(int i=0;i<f;i++){
x[i]=g[i].first;
y[i]=g[i].second;
}
ll dp[f][f+1];//i個目まで考えて、i個目の壁を通るとしたらそれがj回目の通る
for(int i=0;i<f;i++){
for(int j=0;j<=f;j++){
dp[i][j]=0;
}
}
for(int i=0;i<f;i++){
ll tmp=0;
for(int j=1;j<=i+1;j++){
dp[i][j]=COM(x[i]+y[i],x[i]);
for(int k=0;k<i;k++){
if(x[i]>=x[k]&&y[i]>=y[k]){
dp[i][j]-=dp[k][j]*COM(x[i]-x[k]+y[i]-y[k],x[i]-x[k])%mod;
dp[i][j]%=mod;
dp[i][j]+=mod;
dp[i][j]%=mod;
}
}
dp[i][j]-=tmp;
dp[i][j]%=mod;
dp[i][j]+=mod;
dp[i][j]%=mod;
tmp+=dp[i][j];
tmp%=mod;
}
}
vector<ll> ans(f);
for(int i=0;i<f;i++){
ans[i]=dp[f-1][i+1];
}
return ans;
}
int main() {
/* mod は 1e9+7 */
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
cout<< fixed << setprecision(10);
COMinit();
ll n,m;
cin>>n>>m;
ll l,k;
cin>>l>>k;
assert(1<=n&&n<=200000&&0<=m&&m<=min(n-1,100000ll)&&0<=l&&l<=min((n+1)*(n+1),100ll)&&0<=k&&k<=100000);
vector<pair<ll,ll>> z(m+2);
map<pair<ll,ll>,ll> check;
for(int i=0;i<m;i++){
cin>>z[i].first>>z[i].second;
assert(z[i].first>0&&z[i].first<n&&z[i].second>0&&z[i].second<n);
if(i!=0){
assert(z[i-1].first<z[i].first&&z[i-1].second<z[i].second);
}
check[z[i]]=1;
}
z[m].first=0;
z[m].second=0;
z[m+1].first=n;
z[m+1].second=n;
sor(z);
vector<ll> x(m+2);
vector<ll> y(m+2);
for(int i=0;i<m+2;i++){
x[i]=z[i].first;
y[i]=z[i].second;
}
vector<vector<pair<ll,ll>>> g(m+1);
map<pair<ll,ll>,ll> d;
for(int i=0;i<l;i++){
ll x1,y1;
cin>>x1>>y1;
if(x1==0&&y1==0){
assert(x1==-100);
}
if(x1==n&&y1==n){
assert(x1==-100);
}
assert(0<=x1&x1<=n&&0<=y1&&y1<=n);
pair<ll,ll> tmp;
tmp.first=x1;
tmp.second=y1;
if(d[tmp]!=0){
assert(d[tmp]==0);
}
d[tmp]++;
if(check[tmp]==1){
k--;
continue;
}
auto iter=upper_bound(all(x),x1);
ll tmp2=iter-x.begin()-1;
if(x[tmp2]==x1){
if(y[tmp2]>y1){
if(y[tmp2-1]<=y1){
pair<ll,ll> tmp;
tmp.first=x1-x[tmp2-1];
tmp.second=y1-y[tmp2-1];
g[tmp2-1].push_back(tmp);
}
}
if(y[tmp2]<y1){
if(y[tmp2+1]>=y1){
pair<ll,ll> tmp;
tmp.first=x1-x[tmp2];
tmp.second=y1-y[tmp2];
g[tmp2].push_back(tmp);
}
}
}
else{
if(y[tmp2]<=y1&&y[tmp2+1]>=y1){
pair<ll,ll> tmp;
tmp.first=x1-x[tmp2];
tmp.second=y1-y[tmp2];
g[tmp2].push_back(tmp);
}
}
}
vector<ll> ans(l+1);
ans[0]=1;
ll zero=1;
for(int i=0;i<m+1;i++){
if(int(g[i].size())==0){
zero*=COM(x[i+1]-x[i]+y[i+1]-y[i],x[i+1]-x[i]);
zero%=mod;
}
else{
vector<ll> ans2=grid(x[i+1]-x[i],y[i+1]-y[i],g[i]);
vector<ll> tmp(l+1);
for(int j=0;j<=l;j++){
for(int k=0;k<int(ans2.size());k++){
if(j+k<=l){
tmp[j+k]+=(ans[j]*ans2[k])%mod;
tmp[j+k]%=mod;
}
}
}
ans=tmp;
}
}
ll count=0;
for(int i=0;i<int(ans.size());i++){
if(i<=k){
count+=ans[i];
count%=mod;
}
}
cout<<count*zero%mod<<endl;
}