P4594.第2题-斐波那契数列
题目内容
定义超级斐波那契数列如下：给定整数 k，该序列的前 k 项均为 1 ；对于 n>k，第 n 项为前 k 项之和，即
Sn=Sn−1+Sn−2+...+Sn−k
现给定整数 k 和查询次数 q ，每次查询一个正整数 a ，请输出该序列的第 x 项对 109+7 取模后的值。。
输入描述
第一行输入两个整数 k，q(1≤k≤106;1≤q≤2×105)；
此后 q 行，每行输入一个正整数 x(1≤x≤106) 。
输出描述
输出 q 行，每行输出一个整数，表示对应查询的答案对 109+7 取模后的值。
样例1
输入
2 5
1
2
3
4
5
输出
1
1
2
3
5
说明
在这组测试数据中:
- 当 x=1 时，S1=1;
- 当 x=2 时，S2=1;
- 当 x=3 时，S3=S2+S1=1+1=2;
- 当 x=4 时，S4=S3+S2=2+1=3;
- 当 x=5 时，S5=S4+S3=3+2=5。
