流浪者(rover)

战锤2·全面战争 -->(蜥蜴人的 流浪者·纳卡伊 传奇将领) QAQ

好了不扯淡了。。。。

首先观察值域，S <=1e6 （<={2^{20}}）

所以我们可以把次数放进状态

O（{n^2}）暴力好写可以表示每个点，随便写；

关于正解：

设f[i][j]表示到达第i个障碍点并且之前（算上i）共经过j个障碍点的方案数；

将所有障碍点排序（{A_x + A_y < B_x + B_y}）

发现不好直接转移，所以小（shen）学（xian）容斥。

总的 - (<j 和 >j 的方案数)；

即：{C(A_x + A_y - 2,A_x - 1)} -（<j 的已经求出，前缀和一下）-（>j的方案数）

for(int l = 0;l < i;l ++) f[i][j] = f[i][j] - f[l][j] * to[i][l];

#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
#define int long long
#define ll long long
using namespace std;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*f;
}
/*
名利真吾事，纷然过眼休。人生能有死，天道未曾修
百战身皆朽，群心志已酬。一场无限业，何处可优游
*/

const int N = 1e5 + 1000,mod = 1e9 + 7;
int n,m,K,st,QAQ;
ll ans;
ll sum[2100][21],f[2100][21],to[2100][2100];
ll jc[N << 2],inv[N << 2];
ll ksm(ll x,int y)
{
    ll res = 1;
    for(;y;y >>= 1,x = x * x % mod)
        if(y & 1) res = res * x % mod;
    return res;
}
void init()
{
    jc[0] = jc[1] = inv[0] = inv[1] = 1;
    for(int i = 2;i <= 300000;i ++) jc[i] = jc[i - 1] * i % mod;
    inv[300000] = ksm(jc[300000],mod - 2);
    for(int i = 299999;i >= 2;i --) inv[i] = inv[i + 1] * (i + 1) % mod;
}
ll C(ll n,ll m)
{
    if(n < m || n < 0 || m < 0) return 0;
    return jc[n] * inv[m] % mod * inv[n - m] % mod; 
}
struct node{ll x,y;int friend operator < (const node &a,const node &b){return a.x + a.y < b.x + b.y;}}a[N];
signed main()
{
    freopen("rover.in","r",stdin);
    freopen("rover.out","w",stdout);
    init(); n = read(); m = read(); K = read(); st = read();
    int s = st; while(s != 1) {s = (s + 1) / 2; QAQ ++;} 
    for(int i = 1;i <= K;i ++) a[i].x = read(),a[i].y = read();
    a[0] = node{1,1}; a[++ K] = node{n,m};
    sort(a,a + 1 + K); f[0][0] = 1;
    for(int i = 0;i <= K;i ++)
        for(int j = 0;j < i;j ++)
            to[i][j] = C(a[i].x - a[j].x + a[i].y - a[j].y,a[i].x - a[j].x);
    for(int i = 1;i <= K;i ++)
        for(int j = 0;j <= QAQ + 1;j ++)
        {
            f[i][j] = C(a[i].x + a[i].y - 2,a[i].x - 1);
            if(j) f[i][j] = (f[i][j] - sum[i][j - 1] + mod) % mod;
            for(int l = 0;l < i;l ++) f[i][j] = (f[i][j] - f[l][j] * to[i][l] % mod + mod) % mod;
            if(j) sum[i][j] = (sum[i][j - 1] + f[i][j]) % mod;
            else sum[i][j] = f[i][j];
        }
    for(int i = 1;i <= QAQ;i ++,st = (st + 1) / 2) ans = (ans + f[K][i] * st % mod) % mod;
    ans = (ans + ((C(n + m - 2,n - 1) - sum[K][QAQ]) % mod + mod) % mod) % mod;

    cout << ans * ksm(C(n + m - 2,n - 1),mod - 2) % mod;
    fclose(stdin);fclose(stdout);
    return 0;
}