Đội ngũ phát triển của VNG đã huấn luyện một mô hình ngôn ngữ cho trợ lý ảo Kiki (The Voice Assistant for Vietnamese). Trợ lý ảo này có thể trả lời các câu hỏi và yêu cầu từ phía người dùng. Đội ngũ phát triển muốn kiểm tra và đánh giá mức độ hiệu quả của mô hình. Mô hình hoạt động bằng cách sử dụng lại các từ đã dự đoán để tiếp tục dự đoán từ tiếp theo.

Mô hình bắt đầu với một từ có độ tương thích là một số nguyên S, đây là từ tại chỉ số 0 của mô hình. Độ tương thích của từ tại chỉ số $i (1 \leq i)$ được tính như sau:

• Tạo một mảng A chứa độ tương thích của các từ từ 0 đến $i-1$.
• Loại bỏ các từ có độ tương thích bằng $B[i]$ khỏi mảng A.
• Độ tương thích của từ tại chỉ số i là $P + K$, trong đó P là tích của các phần tử trong mảng A và K là số lượng phần tử trong mảng A. Trong trường hợp mảng A không có phần tử nào thì $P = 1$.

Độ tương thích của một câu gồm N từ là tổng độ tương thích của các từ trong câu đó.

Hãy giúp đội ngũ phát triển tính độ tương thích của một câu có độ dài N và độ tương thích của từ bắt đầu bằng S. Vì kết quả có thể rất lớn, bạn chỉ cần in ra phần dư của kết quả khi chia cho 30137.

Đầu vào:

• Dòng đầu tiên chứa hai số nguyên N - độ dài của câu - và S - độ tương thích của từ bắt đầu câu.
• Dòng thứ hai chứa $N-1$ số nguyên, lần lượt là $B[1], B[2], ..., B[N-1]$.

Ràng buộc

• $0 \leq S < 30137$
• $0 \leq B[i] < 30137$ với $1 \leq i \leq N-1$
• $80\%$ số test có $2 \leq N \leq 3000$
• $20\%$ số test còn lại có $2 \leq N \leq 3 \times 10^4$

Đầu ra:

• Một số nguyên duy nhất là độ tương thích của câu theo modulo 30137.

Giải thích: Để tìm độ tương thích của từ tại chỉ số 1, ta thực hiện các bước sau:

• Xây dựng mảng A = $[2]$
• Loại bỏ các từ có độ tương thích bằng $B[1] = 0$ khỏi mảng A. Lúc này mảng A vẫn là $[2]$.
• Độ tương thích của từ tại chỉ số 1 là $2 + 1 = 3$.

Để tìm độ tương thích của từ tại chỉ số 2, ta thực hiện các bước sau:

• Xây dựng mảng A = $[2, 3]$
• Loại bỏ các từ có độ tương thích bằng $B[2] = 0$ khỏi mảng A. Lúc này mảng A vẫn là $[2, 3]$.
• Độ tương thích của từ tại chỉ số 2 là $2 \times 3 + 2 = 8$.

Để tìm độ tương thích của từ tại chỉ số 3, ta thực hiện các bước sau:

• Xây dựng mảng A = $[2, 3, 8]$
• Loại bỏ các từ có độ tương thích bằng $B[3] = 0$ khỏi mảng A. Lúc này mảng A vẫn là $[2, 3, 8]$.
• Độ tương thích của từ tại chỉ số 3 là $2 \times 3 \times 8 + 3 = 51$.

Độ tương thích của câu là $2 + 3 + 8 + 51 = 64$.

Ví dụ 1:

Đầu vào:

4 2
0 0 0

Đầu ra:

64