Submission #19059

#TimeUsernameProblemLanguageResultExecution timeMemory
19059kriiiΩ (kriii4_P3)C++14
0 / 100
0 ms1084 KiB
#include <stdio.h> const long long mod = 1000000007; long long fpow(long long a, long long p) { a = (a % mod + mod) % mod; p = (p % (mod - 1) + mod - 1) % (mod - 1); long long r = 1; while (p){ if (p & 1) r = r * a % mod; a = a * a % mod; p >>= 1; } return r; } int main() { int P,Q,N,K; scanf ("%d %d %d %d",&P,&Q,&N,&K); if (K == 0) puts("0"); else if (K == N) puts("1"); else if (Q == 0) puts("1"); else if (Q == P) puts("0"); else if (Q * 2 == P) printf ("%lld\n",K*fpow(N,-1)); else{ long long v[101]; long long pr = Q * fpow(P,-1), rv = fpow(1-pr,-1); v[0] = 0; v[1] = 1; for (int i=2;i<=N;i++) v[i] = ((v[i-1] - pr * v[i-2]) * rv % mod + mod) % mod; printf ("%lld\n",v[K]*fpow(v[N],-1)%mod); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...