תיאור

ישנם $n + 1$ צמתים, הממוספרים מ-$0$ עד $n$. בהתחלה, אתם נמצאים בצומת $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$).

השורה השנייה מכילה $k - 1$ מספרים שלמים, המייצגים את $t_1, t_2, \dots, t_{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$ שיגורים.