经过初步转化，为计算

$$ F(a,b) = \sum_i \binom{a-i+b-i}{a-i} $$

对一条折线上的 $F(a,b)$ 求总和

本题数据范围 $n\le 1e6$。

经尝试，$F(a,b)$ 满足和组合数 $\binom{a+b}{a}$ 相同的递推式 $F(a,b)=F(a-1,b)+F(a,b-1)$。

经过尝试，$F(a,b)-F(a-1,b)+F(a-2,b) = \binom{a+b}{b}-[a=b+1]$。

之所以 $F$ 具有此性质，也就是 $F$ 可以整式递推，这是因为 $F_b=\sum_a F(a,b)x^a$ 微分有限。事实证明 $F_b$ 存在封闭形式。