Problem Description

有一个无限大的矩形，初始时你在左上角（即第一行第一列），每次你都可以选择一个右下方格子，并瞬移过去（如从下图中的红色格子能直接瞬移到蓝色格子），求到第n行第m列的格子有几种方案，答案对1000000007取模。

 

Input

多组测试数据。

两个整数n,m(2≤n,m≤100000)

 

Output

一个整数表示答案

 

Sample Input

 

Sample Output

 #include <iostream>

 using namespace std;

 typedef long long ll;

 const int mod = 1e9 + ;

 ll quick_pow(ll a, ll b) {      ///快速幂求逆元

     ll ans = ;

     while(b) {

         if(b % ) {

             ans *= a;

             ans %= mod;

         }

         a *= a;

         a %= mod;

         b /= ;

     }

     return ans;

 }

 ll C(int m, int n) {         ///组合数公式：C(m, n) =m!/(n!(m-n)!)

     if(n > m)

         return ;

     ll ans = ;

     for(int i = ; i <= n; i++) {

         ll a, b;

         a = (m - n + i) % mod;

         b = i % mod;

         ans = ans * (a * quick_pow(b, mod - ) % mod) % mod;

     }

     return ans;

 }

 int main() {

     ll m, n;

     while(~scanf("%lld %lld",&n,&m)) {

         printf("%lld\n",C(m+n-,m-));

     }

     return ;

 }