SP9964 PIBO - Fibonacci vs Polynomial

定义一个数列 _Pib_(n) ，具体规则如下： - _Pib_(0) = 1 - _Pib_(1) = 1 - 对于 n ≥ 2，_Pib_(n) = _Pib_(n-1) + _Pib_(n-2) + 多项式 **P**(n) 其中，**P** 是一个多项式。 给定整数 **n** 和多项式 **P**，请计算 _Pib_(n) 对 1,111,111,111 取模后的结果。

第一行输入两个整数 **n** 和 **d**，表示要求的项数和多项式的次数，满足 0 ≤ **n** ≤ 10 $ ^{9} $ ，0 ≤ **d** ≤ 100。 第二行输入 **d**+1 个整数，分别是多项式的系数 **c** $ _{0} $ , **c** $ _{1} $ … **c** $ _{d} $，表示多项式 **P**(x) 可以表示为 Σ**c** $ _{i} $ x $ ^{i} $ 。其中 0 ≤ **c** $ _{i} $ ≤ 100，并且当 **d** ≠ 0 时，**c** $ _{d} $ 不能为 0。

输出一个整数，表示计算出的结果。 **本翻译由 AI 自动生成**