输入

第1行，2个数M,N，中间用空格隔开。（2 <= m,n <= 1000000)

输出

输出走法的数量 Mod 10^9 + 7。

输入样例

2 3

输出样例

3

这种题目暴力是不可能的，
先看题，反正走到终点需要 n + m - 2步；
其中有n - 1步要向下走，其余的向右走，
所以就是C（n + m - 2, n - 1）;
然后就是求组合数了，再加上逆元。

 1 #include <bits/stdc++.h>
 2 #define N 1000000007
 3 #define ll long long int
 4 using namespace std;
 5 
 6 void exgcd(ll a,ll b,ll& d,ll& x,ll& y){
 7     if( !b ) {
 8         d = a;
 9         x = 1; 
10         y = 0; 
11     }else{ 
12         exgcd(b, a%b, d, y, x); 
13         y -= x*(a/b); 
14     }
15 }
16 
17 ll inv(ll a, ll p){
18     ll d, x, y;
19     exgcd(a, p, d, x, y);
20     return d == 1 ? (x+p)%p : -1;
21 }
22 
23 ll cc(ll m, ll n){
24     ll ans = 1;
25     ll cnt = 1;
26     for(ll i = 1; i <= m; i++){
27         ans = (ans*i)%N;
28         cnt = (cnt*n)%N;
29         n --;
30     }
31     return cnt*inv(ans, N)%N;        
32 }
33 
34 int n, m;
35 int main(){
36     cin >> n >> m;
37     cout << cc(min(n,m) - 1, n + m - 2) << endl;
38     return 0;
39 }