Mô tả bài toán

Có $n + 1$ nút, được đánh số từ $0$ đến $n$. Ban đầu, bạn đang ở nút $0$.

Mỗi nút có một cổng dịch chuyển và một bộ đếm, trong đó bộ đếm của nút $p$ (với $0 \le p \le n$) được ký hiệu là $c_p$ (ban đầu tất cả đều bằng $0$). Giá trị của mỗi bộ đếm nằm trong khoảng từ $0$ đến $k - 1$, biểu thị $k$ kiểu dịch chuyển tức thời. Các kiểu dịch chuyển này được điều khiển bởi mảng $t_1, t_2, \dots, t_{k-1}$ như mô tả dưới đây.

Khi đang ở bất kỳ nút $p$ nào, bạn sẽ thực hiện các thao tác sau:

1. Nhấn nút cổng dịch chuyển một lần, cập nhật bộ đếm $c_p$ thành $(c_p + 1) \bmod k$.
2. Nếu giá trị sau khi cập nhật là $c_p = 0$, dịch chuyển đến nút $p + 1$.
3. Ngược lại, nếu $p - t_{c_p} \ge 0$, dịch chuyển đến nút $p - t_{c_p}$ (đặc biệt, khi $t_{c_p} = 0$, việc dịch chuyển đến chính nút hiện tại cũng được tính là một lần dịch chuyển).
4. Ngược lại, quay lại bước một và lặp lại các bước trên.

Bạn dừng lại ngay lập tức khi lần đầu tiên đến được nút $n$ và không tiếp tục thực hiện bất kỳ thao tác nào nữa.

Hãy tính số lần bạn đã sử dụng cổng dịch chuyển kể từ lúc bắt đầu cho đến khi dừng lại (tức là số lần dịch chuyển thành công), và trả về kết quả theo modulo $10^9 + 7$.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa hai số nguyên $n$ ($1 \le n \le 10^9$) và $k$ ($2 \le k \le 1000$).

Dòng thứ hai chứa $k - 1$ số nguyên, biểu thị $t_1, t_2, \dots, t_{k-1}$. Với mọi $i \in [1, k - 1]$, luôn có $0 \le t_i \le \min\{100, n - 1\}$.

Dữ liệu ra

In ra một số nguyên duy nhất biểu thị số lần cổng dịch chuyển đã được sử dụng, lấy kết quả theo modulo $10^9 + 7$.

Ví dụ

Ví dụ 1

2 2
1

4

Ví dụ 2

6 3
0 0

18

Ví dụ 3

114514 5
28 26 70 27

611437835

Ghi chú

Với ví dụ đầu tiên:

• Trạng thái bộ đếm của tất cả các nút là $[0, 0, 0]$, và vị trí hiện tại là ở nút $0$. Nhấn nút cổng dịch chuyển một lần làm thay đổi trạng thái bộ đếm thành $[1, 0, 0]$. Vì $t_1 = 1$ và $0 - 1 < 0$, không có dịch chuyển nào xảy ra, nên nhấn nút cổng dịch chuyển lần nữa làm thay đổi trạng thái bộ đếm thành $[0, 0, 0]$, và bạn dịch chuyển đến nút $1$.
• Vị trí hiện tại là ở nút $1$. Nhấn nút cổng dịch chuyển một lần làm thay đổi trạng thái bộ đếm thành $[0, 1, 0]$. Vì $t_1 = 1$ và $1 - 1 = 0$, bạn dịch chuyển đến nút $0$.
• Vị trí hiện tại là ở nút $0$. Nhấn nút cổng dịch chuyển một lần làm thay đổi trạng thái bộ đếm thành $[1, 1, 0]$. Vì $t_1 = 1$ và $0 - 1 < 0$, không có dịch chuyển nào xảy ra, nên nhấn nút cổng dịch chuyển lần nữa làm thay đổi trạng thái bộ đếm thành $[0, 1, 0]$, và bạn dịch chuyển đến nút $1$.
• Vị trí hiện tại là ở nút $1$. Nhấn nút cổng dịch chuyển một lần làm thay đổi trạng thái bộ đếm thành $[0, 0, 0]$, và bạn dịch chuyển đến nút $2$. Tại thời điểm này, bạn dừng lại ngay lập tức, tổng cộng đã thực hiện $4$ lần dịch chuyển.