E. SUBSEQ - Min - Max - Length

Ta có công thức tính hai loại trọng số của một dãy số như sau:

• Trọng số loại
• Trọng số loại

Trong đó, Min là số có giá trị nhỏ nhất, Max là số có giá trị lớn nhất, Sum là tổng giá trị các số của dãy, Length là số phần tử trong dãy số đó.

Cho dãy số nguyên dương và một giá trị , ta có:

• là tổng trọng số loại của những đoạn con có .
• là tổng trọng số loại của những đoạn con có .

Yêu cầu: Tính giá trị theo modulo .

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên ;
• Dòng thứ hai chứa số nguyên dương . Các số trên một dòng được ghi cách nhau bởi dấu cách.

Dữ liệu ra:

Ghi ra một số nguyên duy nhất là kết quả của bài toán theo modulo .

Ví dụ:

Dữ liệu vào:

4 3
1  2  3  4

Dữ liệu ra:

143

Giải thích:

• Những đoạn con có .
• Những đoạn con có .

Do đó .