คำอธิบายโจทย์

มีโหนด $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$ ครั้ง