AGC001E BBQ Hard

题意：给出 个数对 ，求下列式子的值 ： 答案对 取模。

，，时限 。

---

法一（组合法）

发现 较小，从此处入手。

为 编一个组合意义 ： 从 出发，只能向上或向右走，到达 的方案数。

于是，题目中所求的式子就可以看做 ： 从 出发，到达 的方案数。

平移一下，即改为 ： 从 出发，到达 的方案数。

于是可以改为计算两两点之间的路径条数总和。减去 的贡献后除以 即可

设 为到达 的路径条数，则有如下转移 ：

复杂度为 。

法二（多项式）

简单起见，改记 ，并将三角求和改为方形

利用 进行构造，并尝试对齐次数

求出 之后暴力平方即可。

其中 。

这可以用秦九韶算法快速计算（最后一行从内往外算），总复杂度 。