組み合わせ計算で 64C32 の結果がオーバーフロー


**行いたいこと**  
組み合わせの式 64C32 の結果の下9桁を出力するプログラムをC言語で書きたい

**試したこと**  
以下のようなコードで実行を試みたが、オーバーフローが生じてしまう

[code]

    #include<stdio.h>
    #define ll long long
    
    ll combi(ll n, ll r){
      if (r == 0) {
          return 1;
      }
      return (n - r + 1) * combi(n, r - 1) / r;
    }
    
    int main(){
      printf("%09lld\n",combi(64 ,32 ) );
      return 0;
    }
    
[/code]

解答は 942590534 なのですが、-275878929539273115 のような結果になってしまいます。  
どのようにコードを書けばいいでしょうか。




オーバーフローが起こっているのはこの計算をするときです。

[code]

    (n - r + 1) * combi(n, r - 1) / r
    
[/code]

たとえば `combi(64, 32)` の呼び出しでは以下の計算をすることになりますが、

[code]

    33 * combi(64, 31) / 32
    
[/code]

₆₄C₃₁ = 1,777,090,076,065,542,336 なので、これに 33 を掛けると 2⁶⁴ - 1 =
9,223,372,036,854,775,807 を超えます。

したがって、このオーバーフローが起こらないように計算式を修正する必要があります。剰余がある元で二項係数を求める方法は[色々あります](https://w.atwiki.jp/uwicoder/pages/2118.html)が、今回の場合は[パスカルの三角形](https://ja.wikipedia.org/wiki/%E3%83%91%E3%82%B9%E3%82%AB%E3%83%AB%E3%81%AE%E4%B8%89%E8%A7%92%E5%BD%A2)で求めるのが簡単そうです。つまり、

[code]

    nCr = (n-1)Cr + (n-1)C(r-1)
    
[/code]

という式を元に順番に足し合わせることで求めることができます。これなら途中式が足し算だけなので計算途中に剰余をとることができます。




オーバーフローが起こっているのはこの計算をするときです。

[code]

    (n - r + 1) * combi(n, r - 1) / r
    
[/code]

たとえば `combi(64, 32)` の呼び出しでは以下の計算をすることになりますが、

[code]

    33 * combi(64, 31) / 32
    
[/code]

₆₄C₃₁ = 1,777,090,076,065,542,336 なので、これに 33 を掛けると 2⁶⁴ - 1 =
9,223,372,036,854,775,807 を超えます。

したがって、このオーバーフローが起こらないように計算式を修正する必要があります。剰余がある元で二項係数を求める方法は[色々あります](https://w.atwiki.jp/uwicoder/pages/2118.html)が、今回の場合は[パスカルの三角形](https://ja.wikipedia.org/wiki/%E3%83%91%E3%82%B9%E3%82%AB%E3%83%AB%E3%81%AE%E4%B8%89%E8%A7%92%E5%BD%A2)で求めるのが簡単そうです。つまり、

[code]

    nCr = (n-1)Cr + (n-1)C(r-1)
    
[/code]

という式を元に順番に足し合わせることで求めることができます。これなら途中式が足し算だけなので計算途中に剰余をとることができます。

