Сипаттама

$0$-ден $n$-ге дейін нөмірленген $n + 1$ түйін бар. Бастапқыда сіз $0$-ші түйінде тұрсыз.

Әрбір түйінде портал және есептегіш бар, мұндағы $p$ түйінінің ($0 \le p \le n$) есептегіші $c_p$ деп белгіленеді (бастапқыда барлығы $0$-ге тең). Әрбір есептегіштің мәндер ауқымы $0$ мен $k - 1$ аралығында болады, бұл телепортация әдістерінің $k$ түрін білдіреді. Бұл телепортация әдістері төменде сипатталғандай $t_1, t_2, \dots, t_{k-1}$ массиві арқылы басқарылады.

Кез келген $p$ түйінінде болған кезде сіз келесі амалдарды орындайсыз:

1. Портал батырмасын бір рет басып, $c_p$ есептегішін $(c_p + 1) \bmod k$ мәніне жаңартасыз.
2. Егер жаңартылған $c_p = 0$ болса, $p + 1$ түйініне телепортацияланасыз.
3. Әйтпесе, егер $p - t_{c_p} \ge 0$ болса, $p - t_{c_p}$ түйініне телепортацияланасыз (атап айтқанда, $t_{c_p} = 0$ болғанда, өзіңізге телепортациялану да бір телепортация болып есептеледі).
4. Әйтпесе, бірінші қадамға оралып, жоғарыдағы қадамдарды қайталайсыз.

Сіз $n$ түйініне алғаш рет жеткен кезде бірден тоқтайсыз және ешқандай амалды жалғастырмайсыз.

Басынан бастап тоқтағанға дейін порталды қанша рет пайдаланғаныңызды (яғни сәтті телепортациялар санын) есептеп, нәтижені $10^9 + 7$ модулі бойынша шығарыңыз.

Кіріс деректер

Кірістің бірінші жолында екі бүтін $n$ ($1 \le n \le 10^9$) және $k$ ($2 \le k \le 1000$) сандары берілген.

Екінші жолда $t_1, t_2, \dots, t_{k-1}$ мәндерін білдіретін $k - 1$ бүтін сан берілген. Кез келген $i \in [1, k - 1]$ үшін $0 \le t_i \le \min\{100, n - 1\}$ орындалады.

Шығыс деректер

Порталдың қанша рет пайдаланылғанын білдіретін, $10^9 + 7$ модулі бойынша алынған бір бүтін санды шығарыңыз.

Мысалдар

1-мысал

2 2
1

4

2-мысал

6 3
0 0

18

3-мысал

114514 5
28 26 70 27

611437835

Ескертпе

Бірінші мысал үшін:

• Барлық түйін есептегіштерінің күйі $[0, 0, 0]$, ал бастапқы орын — $0$-ші түйін. Портал батырмасын бір рет басу есептегіш күйін $[1, 0, 0]$ етеді. $t_1 = 1$ және $0 - 1 < 0$ болғандықтан, телепортация орын алмайды, сондықтан портал батырмасын қайта басу есептегіш күйін $[0, 0, 0]$ етеді де, сіз $1$-ші түйінге телепортацияланасыз.
• Қазіргі орын — $1$-ші түйін. Портал батырмасын бір рет басу есептегіш күйін $[0, 1, 0]$ етеді. $t_1 = 1$ және $1 - 1 = 0$ болғандықтан, сіз $0$-ші түйінге телепортацияланасыз.
• Қазіргі орын — $0$-ші түйін. Портал батырмасын бір рет басу есептегіш күйін $[1, 1, 0]$ етеді. $t_1 = 1$ және $0 - 1 < 0$ болғандықтан, телепортация орын алмайды, сондықтан портал батырмасын қайта басу есептегіш күйін $[0, 1, 0]$ етеді де, сіз $1$-ші түйінге телепортацияланасыз.
• Қазіргі орын — $1$-ші түйін. Портал батырмасын бір рет басу есептегіш күйін $[0, 0, 0]$ етеді де, сіз $2$-ші түйінге телепортацияланасыз. Осы сәтте сіз барлығы $4$ телепортация жасап, бірден тоқтайсыз.