SP13940 PIBO2 - Fibonacci vs Polynomial (HARD)

定义一个序列 _Pib_(n) 如下： - _Pib_(0) = 1 - _Pib_(1) = 1 - 对于其他的 n，有 _Pib_(n) = _Pib_(n-1) + _Pib_(n-2) + **P**(n) 其中，**P** 表示一个多项式。 给定两个参数 **n** 和多项式 **P**，要求计算 _Pib_(n) 对 1,111,111,111 取余后的结果。 建议在解决本题之前先尝试[PIBO](../PIBO/)，因为它的限制条件较低。

第一行输入两个整数 **n** 和 **d**（0 ≤ **n** ≤ 10^5, 0 ≤ **d** ≤ 10），这里 **d** 是多项式的最高次数。 接下来一行包含 **d**+1 个整数 **c** $_{0}$, **c** $_{1}$, …, **c** $_{d}$，表示多项式的各项系数。因此多项式 **P**(x) 可以表示为 Σ**c** $_{i}$ x $^{i}$，其中 0 ≤ **c** $_{i}$ < 1,111,111,111 且 **c** $_{d}$ 不等于 0（除非 **d** 等于 0）。

输出一个整数，即结果值。

- 参数范围：0 ≤ **n** ≤ 10^5, 0 ≤ **d** ≤ 10 - 系数范围：0 ≤ **c** $_{i}$ < 1,111,111,111，且当 **d** 不为 0 时，**c** $_{d}$ 必不为 0。 **本翻译由 AI 自动生成**