| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 19981 |
2016-02-25T08:07:47 Z |
gs12117 |
괄호 (kriii4_R) |
C++ |
|
1140 ms |
8904 KB |
#include<stdio.h>
int n,m;
long long int dp[1001000];
int mod=1000000007;
int mpow(int x,int y){
if(y==0)return 1;
long long int r=mpow(x,y/2);
r*=r;
r%=mod;
if(y%2==1){
r*=x;
r%=mod;
}
return r;
}
int minv(int x){
return mpow(x,mod-2);
}
int main(){
int i;
long long int cat;
scanf("%d%d",&n,&m);
dp[0]=1;
cat=1;
for(i=0;i<n;i++){
dp[i+1]=dp[i]*(m+1);
dp[i+1]%=mod;
if(i%2==0){
dp[i+1]+=mod-cat;
dp[i+1]%=mod;
cat*=i+1;
cat%=mod;
cat*=i+2;
cat%=mod;
cat*=minv(i/2+1);
cat%=mod;
cat*=minv(i/2+2);
cat%=mod;
cat*=m;
cat%=mod;
}
}
printf("%lld",dp[n]);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
346 ms |
8904 KB |
Output is correct |
| 2 |
Correct |
70 ms |
8904 KB |
Output is correct |
| 3 |
Correct |
836 ms |
8904 KB |
Output is correct |
| 4 |
Correct |
936 ms |
8904 KB |
Output is correct |
| 5 |
Correct |
957 ms |
8904 KB |
Output is correct |
| 6 |
Correct |
527 ms |
8904 KB |
Output is correct |
| 7 |
Correct |
596 ms |
8904 KB |
Output is correct |
| 8 |
Correct |
399 ms |
8904 KB |
Output is correct |
| 9 |
Correct |
164 ms |
8904 KB |
Output is correct |
| 10 |
Correct |
40 ms |
8904 KB |
Output is correct |
| 11 |
Correct |
44 ms |
8904 KB |
Output is correct |
| 12 |
Correct |
858 ms |
8904 KB |
Output is correct |
| 13 |
Correct |
811 ms |
8904 KB |
Output is correct |
| 14 |
Correct |
352 ms |
8904 KB |
Output is correct |
| 15 |
Correct |
375 ms |
8904 KB |
Output is correct |
| 16 |
Correct |
344 ms |
8904 KB |
Output is correct |
| 17 |
Correct |
1037 ms |
8904 KB |
Output is correct |
| 18 |
Correct |
1078 ms |
8904 KB |
Output is correct |
| 19 |
Correct |
1140 ms |
8904 KB |
Output is correct |
| 20 |
Correct |
1138 ms |
8904 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
311 ms |
8904 KB |
Output is correct |
| 2 |
Correct |
100 ms |
8904 KB |
Output is correct |
| 3 |
Correct |
205 ms |
8904 KB |
Output is correct |
| 4 |
Correct |
1031 ms |
8904 KB |
Output is correct |
| 5 |
Correct |
647 ms |
8904 KB |
Output is correct |
| 6 |
Correct |
797 ms |
8904 KB |
Output is correct |
| 7 |
Correct |
552 ms |
8904 KB |
Output is correct |
| 8 |
Correct |
310 ms |
8904 KB |
Output is correct |
| 9 |
Correct |
544 ms |
8904 KB |
Output is correct |
| 10 |
Correct |
72 ms |
8904 KB |
Output is correct |
| 11 |
Correct |
895 ms |
8904 KB |
Output is correct |
| 12 |
Correct |
938 ms |
8904 KB |
Output is correct |
| 13 |
Correct |
887 ms |
8904 KB |
Output is correct |
| 14 |
Correct |
420 ms |
8904 KB |
Output is correct |
| 15 |
Correct |
518 ms |
8904 KB |
Output is correct |
| 16 |
Correct |
524 ms |
8904 KB |
Output is correct |
| 17 |
Correct |
86 ms |
8904 KB |
Output is correct |
| 18 |
Correct |
1137 ms |
8904 KB |
Output is correct |
| 19 |
Correct |
1133 ms |
8904 KB |
Output is correct |
| 20 |
Correct |
1140 ms |
8904 KB |
Output is correct |
