Abstract Portal
题目描述
有 n+1 个节点,编号为 0,1,…,n。你最初位于节点 0。每个节点 p 有一个传送门和计数器 cp,所有计数器最初都为 0,取值范围为 0 到 k−1。
给定数组 t1,t2,…,tk−1。在节点 p 上,重复执行以下过程:
- 按一次按钮,令 cp←(cp+1)modk。
- 若新的 cp=0,传送至节点 p+1。
- 否则,若 p−tcp≥0,传送至节点 p−tcp。
- 若不能传送,则留在原地重新按按钮。
每次成功传送计数一次。特别地,tcp=0 时传送回自己也计数;无法传送的按键不计数。第一次到达节点 n 后立即停止。
求成功传送的总次数,对 109+7 取模。
输入格式
第一行两个整数 n,k。第二行 k−1 个整数 t1,…,tk−1。
1≤n≤109,2≤k≤1000,0≤ti≤min(100,n−1)。
输出格式
输出一个整数,表示答案对 109+7 取模的结果。
样例 1
输入
2 2
1
输出
4
样例 2
输入
6 3
0 0
输出
18
样例 3
输入
114514 5
28 26 70 27
输出
611437835