http://acm.fzu.edu.cn/contest/list.php?cid=152
主要是a题, lucas定理, 就这一版能过.. 记录一下代码, 另外两个最短路 一个模拟,没什么记录价值.
//#define txtout
//#define debug
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define mt(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;
const double pi=acos(-1.0);
const double eps=1e-;
const int inf=0x3f3f3f3f;
//const int M=1e7+10; LL pow_mod (LL a, LL n, LL p) {
LL ans = ,t = a;
while (n) {
if (n & ) {
ans = ans * t % p;
}
t = t * t % p;
n >>= ;
}
return ans;
}
LL cal (LL n, LL m, LL p) {
if(m > n-m) m = n - m;
LL ans = ;
for (int i = ; i <= m; i++) {
ans = ans * (n - i + ) % p;
int a = pow_mod(i,p-,p);
ans = ans * a % p;
}
return ans;
}
LL com_mod (LL n,LL m,LL p) {
if (n < m)return ;
return cal(n,m,p);
}
LL lucas (LL n, LL m, LL p) {
LL r = ;
while(n && m && r) {
r = r *com_mod(n%p, m%p, p) % p;
n /= p;
m /= p;
}
return r;
} LL a,d,m,n;
//int c[M];
//LL C(int n,int m) {
// LL result=1;
// for(int i=0; i<m; i++) {
// result*=(n-i);
// }
// for(int i=0; i<m; i++) {
// result/=(1+i);
// }
// return result;
//}
const LL MOD=;
LL solve() {
if(n==){
return a;
}
LL answer=lucas(m+n-,n-,MOD)*a%MOD;
if(n->=) answer+=lucas(m+n-,n-,MOD)*d%MOD;
answer%=MOD;
return answer;
}
int main() {
#ifdef txtout
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif // txtout
// num=sieve(MAXN);
while(~scanf("%I64d%I64d%I64d%I64d",&a,&d,&m,&n)) {
printf("%I64d\n",solve());
}
return ;
}
end