#P4161. Shlw loves matrixI

    ID: 3376 传统题 1000ms 512MiB 尝试: 934 已通过: 297 难度: 7 上传者: 标签>难度分类提高+/省选-线性代数与代数线性递推Kitamasa 算法数论快速幂CF2200Bysubmittersubmitter

Shlw loves matrixI

Shlw loves matrix I

题目描述

给定整数序列的前 kk 项 h0,h1,…,hk−1h_0,h_1,\ldots,h_{k-1},以及系数 a1,a2,…,aka_1,a_2,\ldots,a_k。对于每个 j≥kj\ge k,有

hj=∑i=1kaihj−i.h_j=\sum_{i=1}^k a_i h_{j-i}.

求 hnh_n 对 109+710^9+7 取模后的值。

输入格式

第一行两个整数 n,kn,k(1≤n≤1091\le n\le10^9,1≤k≤2 0001\le k\le2\,000)。

第二行 kk 个整数 a1,a2,…,aka_1,a_2,\dots,a_k。第三行 kk 个整数 h0,h1,…,hk−1h_0,h_1,\dots,h_{k-1}。系数和初值的绝对值均不超过 10910^9。

输出格式

输出一行一个整数,表示 hnh_n 对 109+710^9+7 的非负余数。

样例 #1

样例输入 #1

6 4
3 -1 0 4
-2 3 1 5

样例输出 #1

73

样例说明

给定的初值依次是 h0=−2,h1=3,h2=1,h3=5h_0=-2,h_1=3,h_2=1,h_3=5,递推得到 h4=6h_4=6、h5=25h_5=25、h6=73h_6=73。