#P18067. Abstract Portal

Abstract Portal

Abstract Portal

题目描述

有 n+1n+1 个节点,编号为 0,1,…,n0,1,\ldots,n。你最初位于节点 00。每个节点 pp 有一个传送门和计数器 cpc_p,所有计数器最初都为 00,取值范围为 00 到 k−1k-1。

给定数组 t1,t2,…,tk−1t_1,t_2,\ldots,t_{k-1}。在节点 pp 上,重复执行以下过程:

  1. 按一次按钮,令 cp←(cp+1) mod kc_p\leftarrow(c_p+1)\bmod k。
  2. 若新的 cp=0c_p=0,传送至节点 p+1p+1。
  3. 否则,若 p−tcp≥0p-t_{c_p}\ge0,传送至节点 p−tcpp-t_{c_p}。
  4. 若不能传送,则留在原地重新按按钮。

每次成功传送计数一次。特别地,tcp=0t_{c_p}=0 时传送回自己也计数;无法传送的按键不计数。第一次到达节点 nn 后立即停止。

求成功传送的总次数,对 109+710^9+7 取模。

输入格式

第一行两个整数 n,kn,k。第二行 k−1k-1 个整数 t1,…,tk−1t_1,\ldots,t_{k-1}。

1≤n≤1091\le n\le10^9,2≤k≤10002\le k\le1000,0≤ti≤min⁡(100,n−1)0\le t_i\le\min(100,n-1)。

输出格式

输出一个整数,表示答案对 109+710^9+7 取模的结果。

样例 1

输入

2 2
1

输出

4

样例 2

输入

6 3
0 0

输出

18

样例 3

输入

114514 5
28 26 70 27

输出

611437835