/* * ******************************************************************************************** * AUTHOR : Vijju123 * * Language: C++14 * * Purpose: - * * IDE used: Codechef IDE. * ******************************************************************************************** * Comments will be included in practice problems if it helps ^^ */ #include #include using namespace std; int mod=pow(10,9)+7; int fastExpo(long long a,long long n, int mod) { a%=mod; if(n==2)return a*a%mod; if(n==1)return a; if(n&1)return a*fastExpo(fastExpo(a,n>>1,mod),2,mod)%mod; else return fastExpo(fastExpo(a,n>>1,mod),2,mod); } inline void add(vector > &a,vector > &b,int mod) { for(int i=0;i > &a, vector > &b,int mod,vector > &temp) { assert(a[0].size()==b.size()); int i,j; for(i=0;i > &arr,int power,int mod) { int i,j,k; vector >temp,temp2,temp3; vector init(arr[0].size()); for(i=0;i0) { if(power&1) { multiply(arr,temp3,mod,temp); swap(temp3,temp); } multiply(arr,arr,mod,temp2); swap(arr,temp2); power>>=1; } swap(arr,temp3); } vector primes; int isComposite[1000001]={1,1}; void sieve() { int i,j; for(i=2;i<=1000000;i++) { if(!isComposite[i]) { primes.push_back(i); isComposite[i]=i; } for(j=0;j>n; int p1[n],p2[n]; for(int i=0;i