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\).