#include<bits/stdc++.h>
//#pragma GCC optimize(2,3,"Ofast","-fgcse","-fgcse-lm","-fipa-sra","-ftree-pre","-ftree-vrp","-fpeephole2","-ffast-math","-fsched-spec","unroll-loops","-falign-jumps","-falign-loops","-falign-labels","-fdevirtualize","-fcaller-saves","-fcrossjumping","-fthread-jumps","-funroll-loops","-freorder-blocks","-fschedule-insns","inline-functions","-ftree-tail-merge","-fschedule-insns2","-fstrict-aliasing","-falign-functions","-fcse-follow-jumps","-fsched-interblock","-fpartial-inlining","no-stack-protector","-freorder-functions","-findirect-inlining","-fhoist-adjacent-loads","-frerun-cse-after-loop","inline-small-functions","-finline-small-functions","-ftree-switch-conversion","-foptimize-sibling-calls","-fexpensive-optimizations","inline-functions-called-once","-fdelete-null-pointer-checks","inline","fast-math","unroll-loops")
#pragma GCC target("sse3","sse2","sse","avx","sse4","sse4.1","sse4.2","ssse3","f16c")
#pragma GCC diagnostic error "-fwhole-program","-fcse-skip-blocks","-funsafe-loop-optimizations","-std=c++14"
using namespace std;
#define int long long
int mod=1000000007;
namespace IO{
    char buf[4194304],*p1=buf,*p2=buf,pbuf[4194304],*pp=pbuf;
    inline char gc(){
        return p1==p2&&(p2=(p1=buf)+fread(buf,1,4194304,stdin),p1==p2)?EOF:*p1++;
    }
    inline int read(){
        int x=0;
        char ch=gc(),flag=0;
        while(ch<'0'||ch>'9')
            flag|=(ch=='-'),ch=gc();
        while(ch>='0'&&ch<='9')
            x=(x<<3)+(x<<1)+ch-'0',ch=gc();
        return flag?~x+1:x;
    }
    inline void push(char c){
        if(pp-pbuf==4194304)
            fwrite(pbuf,1,4194304,stdout),pp=pbuf;
        *pp++=c;
    }
    inline void write(int x){
        static int sta[40];
        int top=0;
        if(x<0)
            push('-'),x=-x;
        do
            sta[top++]=x%10,x/=10;
        while(x);
        while(top)
            push(sta[--top]+'0');
    }
    void flush(){
        fwrite(pbuf,pp-pbuf,1,stdout);
    }
}
using namespace IO;
template <typename _Tp>
class Matrix{
	private:
		typedef initializer_list<_Tp> _il_Tp;
		typedef initializer_list<_il_Tp> _il_il_Tp;
	public:
		_Tp **Data=nullptr;
		size_t n,m;
		bool Allocated=false;
		Matrix(){}
		Matrix(size_t _n,size_t _m):n(_n),m(_m){
			Allocate();
		}
		Matrix(_il_il_Tp init){
			*this=init;
		}
		Matrix(const Matrix& arg){
			*this=arg;
		}
		void resize(const size_t& _r,const size_t& _c){
			if(_r==n && _c==m && Allocated)
				return;
			else{
				destroy();
				n=_r;
				m=_c;
				Allocate();
			}
		}
		void Allocate(){
			if(Allocated)
				return;
			Data=new _Tp *[n+1];
			for(unsigned i=0;i<=n;i++)
				Data[i]=new _Tp [m+1];
			for(unsigned i=0;i<=n;i++)
				for(unsigned j=0;j<=m;j++)
					Data[i][j]=0;
			Allocated=true;
		}
		void destroy(){
			if(!Allocated)
				return ;
			for(unsigned i=0;i<=n;i++)
				delete [] (Data[i]);
			delete [] Data;
			Allocated=false;
		}
		void setone(){
			if(!Allocated)
				throw logic_error("Matrix Memory Error: \n Unallocated memory!");
			if(n!=m)
				throw logic_error("Matrix One-setting Error: \nColomn number mismatches row number");
			for(unsigned i=0;i<=n;i++)
				Data[i][i]=1;
		}
		Matrix& operator=(const Matrix& arg){
			resize(arg.n,arg.m);
			for(unsigned i=0;i<=n;i++)
				for(unsigned j=0;j<=m;j++)
					Data[i][j]=arg.Data[i][j];
			return *this;
		}
		Matrix& operator=(_il_il_Tp init){
			size_t r=init.size(),c=0;
			for(_il_Tp il:init)
				c=max(m,il.size());
			resize(r,c);
			int i=1,j;
			for(const _il_Tp &init2:init){
				j=1;
				for(const _Tp &init3:init2){
					Data[i][j]=init3;
					j++;
				}
				i++;
			}
			return *this;
		}
		_Tp* operator[](const size_t ind){
			return Data[ind];
		}
		~Matrix(){
			destroy();
		}
};
template <typename _Tp>
Matrix<_Tp> operator*(const Matrix<_Tp> &a, const Matrix<_Tp> &b){
	if(!a.Allocated || !b.Allocated)
		throw logic_error("Matrix Memory Error: \n Unallocated memory!");
	if(a.m != b.n)
		throw logic_error("Matrix Multiplication Error: \nThe colomn number of the first matrix one (which is %d) mismatches the row number of the second matrix (which is %d)"/*,a.m,b.n*/);
	Matrix<_Tp> c(a.n,b.m);
	for(unsigned k=0;k<=a.m;k++)
		for(unsigned i=0;i<=c.n;i++)
			for(unsigned j=0;j<=c.m;j++)
				(c.Data[i][j])=((c.Data[i][j])+((a.Data[i][k])*(b.Data[k][j])))%mod;
	return c;
}
template <typename _Tp>
Matrix<_Tp> operator*(Matrix<_Tp> a, const _Tp b){
	if(!a.Allocated)
		throw logic_error("Matrix Memory Error: \n Unallocated memory!");
	for(unsigned i=0;i<=a.n;i++)
		for(unsigned j=0;j<=a.m;j++)
			(a.Data[i][j])=((a.Data[i][j])*b)%mod;
	return a;
}
template <typename _Tp>
Matrix<_Tp> operator+(const Matrix<_Tp> &a, const Matrix<_Tp> &b){
	if(!a.Allocated || !b.Allocated)
		throw logic_error("Matrix Memory Error: \n Unallocated memory!");
	if(a.m != b.m or a.n != b.n)
		throw logic_error("Matrix Multiplication Error: \nThe row/colomn number of the first matrix one (which is %d) mismatches the row/colomn number of the second matrix (which is %d)"/*,a.m,b.n*/);
	Matrix<_Tp> c(a.n,b.n);
	for(unsigned i=0;i<=c.n;i++)
		for(unsigned j=0;j<=c.m;j++)
			(c.Data[i][j])=(((a.Data[i][j])+(b.Data[i][j]))%mod);
	return c;
}
template <typename _Tp>
Matrix<_Tp> quick_pow(Matrix<_Tp> a,int p){
	Matrix<int> ret(a.n,a.n);
	ret.setone();
	while(p){
		if(p&1)
			ret=ret*a;
		p>>=1;
		a=a*a;
	}
	return ret;
}
template <typename _Tp>
ostream& operator<<(ostream& os,const Matrix<_Tp> &arg){
	for(unsigned int i=0;i<=arg.n;i++,os<<'\n')
		for(unsigned int j=0;j<=arg.m;j++)
			os<<arg.Data[i][j]<<' ';
	return os;
}
int N,K;
Matrix<int> G,p,A,B,C;
void solve(int k){
	if(k==1){
		p=G;
		A.setone();
		return ;
	}
	int _p=k>>1;
	solve(_p);
	C = C + C*p + B*p*(2*_p) + A*p*(_p*_p%mod);
	B = B + B*p + A*p*_p;
	A = A + A*p;
	p=p*p;
	if(k&1){
		A=A+p;
		B=B+p*(k-1);
		C=C+p*((k-1)*(k-1)%mod);
		p=p*G;
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int M,Q;
	N=read(),M=read(),K=read(),Q=read();
	A.resize(N,N);
	B.resize(N,N);
	C.resize(N,N);
	G.resize(N,N);
	p.resize(N,N);
	for(int i=1;i<=M;i++){
		int u=read(),v=read();
		G[u][v]++;
	}
	solve(K+1);
	while(Q--){
		int x=read(),y=read();
		write(C[x][y]);
		push('\n');
	}
	flush();
	return 0;
}

本身应该没有问题，但是本人不太会卡常，常用卡常技巧比如pragma,快读还有一些其他的用过了，用处不大，有无大佬帮忙看看,谢谢