الوصف

يوجد $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$ عمليات انتقال آني.