Deskripsi

Terdapat $n + 1$ simpul, yang dinomori dari $0$ hingga $n$. Awalnya, Anda berada di simpul $0$.

Setiap simpul memiliki sebuah portal dan sebuah penghitung, di mana penghitung untuk simpul $p$ (dengan $0 \le p \le n$) dinyatakan sebagai $c_p$ (awalnya semua bernilai $0$). Rentang nilai setiap penghitung adalah antara $0$ dan $k - 1$, yang mewakili $k$ jenis metode teleportasi. Metode teleportasi ini dikendalikan oleh array $t_1, t_2, \dots, t_{k-1}$, sebagaimana dijelaskan di bawah ini.

Ketika Anda berada di simpul $p$ mana pun, Anda akan melakukan operasi berikut:

1. Tekan tombol portal satu kali, memperbarui penghitung $c_p$ menjadi $(c_p + 1) \bmod k$.
2. Jika nilai yang telah diperbarui adalah $c_p = 0$, berteleportasilah ke simpul $p + 1$.
3. Jika tidak, apabila $p - t_{c_p} \ge 0$, berteleportasilah ke simpul $p - t_{c_p}$ (secara khusus, ketika $t_{c_p} = 0$, berteleportasi ke diri sendiri juga dihitung sebagai satu kali teleportasi).
4. Jika tidak, kembali ke langkah pertama dan ulangi langkah-langkah di atas.

Anda langsung berhenti ketika pertama kali mencapai simpul $n$ dan tidak melanjutkan operasi apa pun.

Hitunglah berapa kali Anda menggunakan portal sejak awal hingga berhenti (yaitu, banyaknya teleportasi yang berhasil), dan kembalikan hasilnya modulo $10^9 + 7$.

Masukan

Baris pertama masukan berisi dua bilangan bulat $n$ ($1 \le n \le 10^9$) dan $k$ ($2 \le k \le 1000$).

Baris kedua berisi $k - 1$ bilangan bulat, yang menyatakan $t_1, t_2, \dots, t_{k-1}$. Untuk setiap $i \in [1, k - 1]$, berlaku bahwa $0 \le t_i \le \min\{100, n - 1\}$.

Keluaran

Keluarkan sebuah bilangan bulat yang menyatakan berapa kali portal digunakan, dengan hasil diambil modulo $10^9 + 7$.

Contoh

Contoh 1

2 2
1

4

Contoh 2

6 3
0 0

18

Contoh 3

114514 5
28 26 70 27

611437835

Catatan

Untuk contoh pertama:

• Status penghitung semua simpul adalah $[0, 0, 0]$, dan posisi berada di simpul $0$. Menekan tombol portal satu kali mengubah status penghitung menjadi $[1, 0, 0]$. Karena $t_1 = 1$ dan $0 - 1 < 0$, tidak ada teleportasi yang terjadi, sehingga menekan tombol portal sekali lagi mengubah status penghitung menjadi $[0, 0, 0]$, dan Anda berteleportasi ke simpul $1$.
• Posisi sekarang berada di simpul $1$. Menekan tombol portal satu kali mengubah status penghitung menjadi $[0, 1, 0]$. Karena $t_1 = 1$ dan $1 - 1 = 0$, Anda berteleportasi ke simpul $0$.
• Posisi sekarang berada di simpul $0$. Menekan tombol portal satu kali mengubah status penghitung menjadi $[1, 1, 0]$. Karena $t_1 = 1$ dan $0 - 1 < 0$, tidak ada teleportasi yang terjadi, sehingga menekan tombol portal sekali lagi mengubah status penghitung menjadi $[0, 1, 0]$, dan Anda berteleportasi ke simpul $1$.
• Posisi sekarang berada di simpul $1$. Menekan tombol portal satu kali mengubah status penghitung menjadi $[0, 0, 0]$, dan Anda berteleportasi ke simpul $2$. Pada titik ini, Anda langsung berhenti, setelah melakukan total $4$ kali teleportasi.