Per đang lên kế hoạch đi du lịch bằng tàu.

Chuyến du lịch kéo dài ~n~ ngày. Với mỗi ngày, Per hoặc có thể trả tiền vé thông thường — loại ~A~, hoặc sử dụng vé một ngày loại ~B~.

Loại vé thông thường ~A~ được biểu diễn bằng mảng số nguyên ~a~ — ngày thứ ~i~ giá vé sẽ là ~a_i~.

Loại vé một ngày ~B~ được bán theo lô gồm ~d~ vé, giá cả lô là ~p~ đồng. Per được tùy ý số lượng mua nhưng chỉ có thể mua theo từng lô. Vé đã mua được sử dụng vào ngày bất kỳ theo ý muốn. Khi kết thúc chuyến đi, có thể còn thừa vé loại ~B~.

Per đang muốn tính toán chi phí tối thiểu cho chuyến du lịch gồm ~n~ ngày này. Các bạn hãy giúp Per thử nhé!

Lưu ý rằng ngày nào cũng phải có một trong hai loại vé để sử dụng!

Dữ liệu vào

• Dòng đầu chứa ba số nguyên ~n~, ~d~, ~p~ — số lượng phần tử của mảng ~a~ và các tham số ~d~, ~p~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_i~ — mô tả mảng ~a~.

Kết quả

In ra đáp án duy nhất trong một dòng.

Ví dụ

Đầu vào:

5 2 10
7 1 6 3 6

Đầu ra:

20

Giải thích: Ta sẽ mua ~1~ lô vé loại ~B~ dùng vào các ngày ~1~ và ~3~, các ngày còn lại thanh toán vé loại ~A~. Tổng chi phí là ~(10 \times 1) + (1 + 3 + 6) = 20~.

Giới hạn

• ~1 \le n, d \le 2 \cdot 10^5~
• ~1 \le p \le 10^9~
• ~1 \le a_i \le 10^9~

Kết quả có thể lên tới ~2 \cdot 10^{14}~, nên không vừa trong số nguyên 32 bit.

QNT và Haky đang giúp anh Domixi bán khô gà bã mía – một công việc phức tạp mà chỉ khi hát bài Nà ná na thì mới xong được .

Hai anh em quyết định tâm là kết hợp với nhau: QNT sẽ đóng bã mía, còn Haky sẽ đè tem. QNT được giao một vài đống bã mía đánh số từ ~1~ đến ~N~ (~1 \le N \le 10^5~). Haky có một bộ tem – Sử dụng để đóng lên các hộp khô gà. Giữa QNT và Haky có một mặt bàn để đặt các hộp đã đóng bã mía.

Ở mỗi bước, một trong hai việc sau sẽ xảy ra:

• QNT: Lấy một bã mía từ đống bã mía, bôi phẩm màu và gia vị, rồi đặt lên mặt bàn làm thành hộp khô gà. Khi đặt bã mía đã chế biến, QNT phải hoặc (i) đặt khô gà lên trên một chồng khô gà không rỗng đã có, hoặc (ii) tạo một chồng khô gà mới ở bên phải tất cả các chồng khô gà hiện tại.
• Haky: Lấy một bịch khô gà từ đỉnh của chồng khô gà ngoài cùng bên trái. Haky đè tem, rồi đặt lên trên chồng sản phẩm cuối.

Mục tiêu là chồng sản phẩm cuối chứa toàn bộ khô gà theo thứ tự: Số nhỏ nhất ở dưới cùng và số lớn nhất ở trên cùng. Có thể không thể đạt được mục tiêu này cho toàn bộ chồng đĩa, vậy hãy xác định độ dài tiền tố dài nhất của thứ tự đầu vào sao cho mục tiêu vẫn có thể đạt được.

Input

Dòng đầu tiên chứa số nguyên ~N~ (~1 \le N \le 10^5~).

~N~ dòng tiếp theo mô tả thứ tự các bịch bã mía trong chồng khô gà của QNT, trong đó số đầu tiên là bịch ở đỉnh chồng.

Output

In ra độ dài tiền tố dài nhất của chồng khô gà đầu vào có thể được xử lý thành công sao cho các bịch khô gà kết thúc được sắp xếp đúng thứ tự trong chồng sản phẩm cuối.

Example

Input

5
4
5
2
3                                                                                                                                                                                               
1

Output

4

Vừa đi chơi về, QNT muốn làm món nước hoa quả thần thánh để giải khát, ăn kèm khô gà được anh DoMixi gửi.

Trong tủ lạnh đang có hai hộp quả: cam và dưa hấu (không giới hạn số lượng). QNT thích cả hai loại quả nên sẽ tìm cách sử dụng cả hai nhiều nhất có thể.

Bình đựng của QNT có thể chứa tối đa trọng lượng là ~w~ đơn vị. Thêm vào một quả cam sẽ tăng ~x~ đơn vị, thêm vào một quả dưa hấu sẽ tăng ~y~ đơn vị. Ngoài ra, QNT có thể sử dụng máy ép một lần duy nhất để làm giảm trọng lượng trong bình đi một nửa (trọng lượng được làm tròn xuống).

Cụ thể, bình bắt đầu với trọng lượng ~0~. Tại mỗi bước, QNT có thể:

• thêm một quả cam: trọng lượng ~v~ trở thành ~v + x~;
• thêm một quả dưa hấu: trọng lượng ~v~ trở thành ~v + y~;
• dùng máy ép (nhiều nhất một lần trong cả quá trình): trọng lượng ~v~ trở thành ~\lfloor v/2 \rfloor~.

Trọng lượng trong bình không bao giờ được vượt quá ~w~. QNT không bắt buộc phải dùng máy ép.

Vì muốn dùng thật nhiều nước hoa quả, QNT muốn xác định trọng lượng lớn nhất có thể đạt được trong bình. Các bạn hãy giúp QNT nhé! Khô gà mà không có nước uống kèm thì quả là uổng!

Dữ liệu vào

Dòng đầu tiên và duy nhất chứa ba số nguyên ~w~, ~x~, ~y~ — trọng lượng tối đa của bình và khối lượng của hai loại quả.

Kết quả

In ra đáp án trên một dòng.

Ví dụ

Đầu vào:

8 5 6

Đầu ra:

8

Giải thích: QNT dùng trước một quả dưa hấu, lúc này trọng lượng bình là ~6~. Dùng máy ép, trọng lượng còn ~\lfloor 6/2 \rfloor = 3~. Sau đó thêm vào một quả cam, tổng trọng lượng là ~3 + 5 = 8~. Nếu không dùng máy ép thì nhiều nhất chỉ đạt được ~6~.

Giới hạn

• ~1 \le w \le 5 \cdot 10^6~
• ~1 \le x, y \le w~

Trong đợt họp fan tập thể, Anh Domixi đã nghĩ ra một bài tập thể dục mới cho các anh em Do tộc!

Giống như trước, ~N~ anh em (~1 \le N \le 10^4~) đang đứng thành một hàng. Bạn thứ ~i~ từ trái sang tương ứng với chỉ số ~i~ với mỗi ~1 \le i \le N~. Anh Domixi bảo mọi người lặp lại bước sau cho đến khi các bạn trở về đúng thứ tự ban đầu.

Cho một hoán vị ~A~ có độ dài ~N~, các anh em sẽ đổi vị trí sao cho bạn thứ ~i~ từ trái sang trước khi đổi sẽ trở thành bạn thứ ~A_i~ từ trái sang sau khi đổi.

Ví dụ, nếu ~A = (1, 2, 3, 4, 5)~ thì các bạn chỉ thực hiện một bước. Nếu ~A = (2, 3, 1, 5, 4)~, thì các bạn thực hiện sáu bước. Thứ tự các bạn từ trái sang phải sau mỗi bước như sau:

• 0 bước: ~(1, 2, 3, 4, 5)~
• 1 bước: ~(3, 1, 2, 5, 4)~
• 2 bước: ~(2, 3, 1, 4, 5)~
• 3 bước: ~(1, 2, 3, 5, 4)~
• 4 bước: ~(3, 1, 2, 4, 5)~
• 5 bước: ~(2, 3, 1, 5, 4)~
• 6 bước: ~(1, 2, 3, 4, 5)~

Hãy tìm tổng của tất cả các số nguyên dương ~K~ sao cho tồn tại một hoán vị có độ dài ~N~ yêu cầu các bạn thực hiện đúng ~K~ bước.

Vì kết quả có thể rất lớn, hãy in ra đáp án theo modulo ~M~ (~10^8 \le M \le 10^9 + 7~, ~M~ là số nguyên tố).

Input

Dòng duy nhất chứa hai số nguyên ~N~ và ~M~ (~1 \le N \le 10^4~, ~10^8 \le M \le 10^9 + 7~, ~M~ là số nguyên tố) – độ dài hoán vị và số modulo.

Output

In ra một số nguyên duy nhất là tổng của tất cả các giá trị ~K~ hợp lệ theo modulo ~M~.

Example

Input

5 1000000007

Output

21              

Note

Ở test ví dụ với ~N = 5~, các giá trị ~K~ có thể đạt được là ~{1, 2, 3, 4, 5, 6}~, tương ứng với các cách phân hoạch ~5~ thành các chu trình có bội chung nhỏ nhất khác nhau. Tổng là ~1 + 2 + 3 + 4 + 5 + 6 = 21~.