パスカルの三角形を長方形で書く． \(r\) 行 \(c\) 列が \({}_{r+c}C_{r}\) となる． 長方形領域の和は，左上を\(\,(0,0)\,\) で固定して， 累積和と同様に計算すると良い．
パスカルの三角形の性質
\(\sum{r \in [0,R] } f_{r,c} = f_{R,c+1}\) となることを用いる． これを \(c\) を動かして和をとる． 行と列を入れ替えて同様のこともすると， 左上を \(\,(0,0)\,\) で固定したときの長方形領域の和が求まる．
\begin{align} ans &= \sum_{(r,c) \in [r1,r2+1) \times [c1, c2+1)} f(r,c) \\ &= \sum_{(r,c) \in [r1,r2+1) \times [c1, c2+1)} {}_{r+c} C _{r}. \end{align}
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
Comb<mint, (ll)2e6+5> co;
ll r0, r1, c0, c1;
cin >> r0 >> c0 >> r1 >> c1;
r1++, c1++;
auto rect = [&](ll r, ll c) -> mint {
return co.nCr(r+c, c) - 1;
};
mint ans;
ans += rect(r1,c1);
ans -= rect(r1,c0);
ans -= rect(r0,c1);
ans += rect(r0,c0);
cout << ans.val() << endl;
return 0;
}
