Contest ôn HSG 9-10 #10

Minh có một chiếc máy tính bị "hỏng". Ban đầu, máy hiển thị số \(1\). Máy chỉ có thể hiển thị tối đa \(k\) chữ số. Minh lần lượt thực hiện liên tiếp \(n\) phép nhân. Với mỗi phép nhân, Minh lấy số hiện tại (theo kết quả hiển thị trên máy) nhân với lần lượt từng số \(a_1, a_2, \ldots, a_n\) theo quy tắc sau:

• Giả sử ta đang xét phép nhân thứ \(i\) (với số \(a_i\)).
• Gọi \(D\) là giá trị hiển thị trên máy sau khi thực hiện phép tính nhân với các số trước (\(a_1, a_2, a_3, \ldots, a_{i-1}\)).
• Nếu kết quả \(D \times a_i\) có từ \(k+1\) chữ số trở lên, máy bị tràn số, và hiển thị số \(1\).
• Ngược lại, nếu không tràn số, máy hiển thị chính xác kết quả tích tính được.

Yêu cầu: Cho biết \(n\), \(k\) và dãy \(a\). Hãy tìm giá trị \(D\) sau toàn bộ \(n\) phép tính.

Input

• Dòng đầu chứa hai số nguyên \(n, k\) \((1 \leq n \leq 10000;\ 1 \leq k \leq 18)\).
• Dòng tiếp theo chứa \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) \((1 \leq a_i < 10^k)\).

Output

• In ra kết quả cuối cùng sau \(n\) phép tính nhân.

Example

5 2
7 13 3 2 5

10

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(k \leq 9\).
• Subtask \(2\) (\(50\%\) số điểm): \(k \leq 18\).

Quỳnh đang tham gia một trò chơi bắn bóng bay tính điểm. Trên bầu trời có \(N\) quả bóng bay được đánh số từ \(1\) đến \(N\). Tại thời điểm bắt đầu trò chơi (\(t=0\)), quả bóng thứ \(i\) đang ở độ cao \(H_i\) và cứ sau mỗi giây, nó lại bay cao thêm \(S_i\) (đơn vị độ cao). Trò chơi diễn ra như sau:

• Tại thời điểm bắt đầu (\(t=0\)), Quỳnh bắn nổ một quả bóng bất kỳ.
• Sau đó, cứ mỗi giây trôi qua, tại các thời điểm \(t=1, t=2, \ldots, t=N-1\); Quỳnh lần lượt bắn nổ từng quả bóng.
• Trò chơi sẽ kết thúc vào thời điểm \(t=N-1\), khi Quỳnh đã bắn hết bóng.

Điểm chung cuộc của trò chơi lấy theo độ cao lớn nhất trong số \(N\) độ cao của các quả bóng tại thời điểm bị Quỳnh bắn nổ. Điểm càng thấp càng thể hiện "trình" bắn súng điêu luyện. Quỳnh sẽ chọn thứ tự bắn các quả bóng để đạt được điểm số thấp nhất.

Yêu cầu: Tìm điểm số chung cuộc nhỏ nhất có thể đạt được.

Input

• Dòng đầu tiên chứa số nguyên \(N\) \((1 \leq N \leq 10^5)\).
• \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(H_i, S_i\) \((1 \leq H_i, S_i \leq 10^9)\) mô tả độ cao ban đầu và tốc độ bay lên của quả bóng thứ \(i\).

Output

• Một số nguyên duy nhất là điểm số chung cuộc nhỏ nhất tìm được.

Example

4
12 4
5 6
21 2
14 7

23

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \leq 8\).
• Subtask \(2\) (\(30\%\) số điểm): \(N \leq 300\).
• Subtask \(3\) (\(40\%\) số điểm): không có ràng buộc thêm.

Quang đố Trí một bài toán về tổ hợp trên chuỗi ký tự. Quang đưa cho Trí một chuỗi \(S\) độ dài \(n\) gồm các ký tự a, b, c và ?. Mỗi ký tự ? có thể được thay thế bằng một trong ba ký tự a, b hoặc c. Giả sử chuỗi \(S\) có \(k\) ký tự ?, Trí sẽ tạo ra được tổng cộng \(3^k\) chuỗi khác nhau chỉ gồm các ký tự a, b, và c.

Với mỗi chuỗi được tạo ra, ta xét số lượng "xâu con abc" – là những xâu con không liên tiếp có ba ký tự của nó nằm tại các chỉ số \((i, j, k)\) thỏa mãn: \(1 \leq i < j < k \leq n\) và \(S[i]=\) a, \(S[j]=\) b, \(S[k]=\) c.

Yêu cầu: Đếm số lượng "xâu con abc" trên tất cả các chuỗi có thể tạo ra từ \(S\). Do kết quả có thể rất lớn, hãy in ra kết quả chia lấy dư cho \(10^9 + 7\).

Input

• Dòng đầu chứa số nguyên \(n\) \((1 \leq n \leq 2 \times 10^5)\).
• Dòng thứ hai chứa chuỗi ký tự \(S\).

Output

• Dòng duy nhất đưa ra kết quả tính được.

Example

6
ac?b?c

24

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 12\).
• Subtask \(2\) (\(20\%\) số điểm): xâu \(S\) không chứa ký tự ?.
• Subtask \(3\) (\(30\%\) số điểm): xâu \(S\) chỉ chứa ký tự ?.
• Subtask \(4\) (\(20\%\) số điểm): không có ràng buộc gì thêm.