THỰC HÀNH

Ta có dãy thứ tự trong đó mỗi ngày số nhà sau:

Trọng số lẻi 1 = Min × Max × Length

Trọng số lẻi 2 = Min × Max × Sum

Trọng độ, Min là số cỏ gái trị nhỏ nhất, Max là số cỏ gái trị lớn nhất, Sum là tổng giá trị số cưa dãy, Length là số phấn tử trong dãy số đó.

Cho dãy n số nguyên dương a₁, a₂, ..., aₙ và môt giá trị S, ta có:

• P₁ là tổng trọng số lẻi 1 cưa những dồn cỏn aᵢ, aᵢ₊₁, ..., aⱼ (1 ≤ i ≤ j ≤ n) có Sum > S.
• P₂ là tổng trọng số lẻi 2 cưa những dồn cỏn aᵢ, aᵢ₊₁, ..., aⱼ (1 ≤ i ≤ j ≤ n) có Sum ≤ S.

Yêu cầu: Tính giá trị P₁ + P₂ theo modulo 10⁹ + 7.

Input:

• Dòng đầu tiên chứa hai số nguyên n, S (1 ≤ n ≤ 5.10⁴, 0 ≤ S ≤ 10¹⁸);
• Dòng thứ hai chứa n số nguyên dương aᵢ (1 ≤ aᵢ ≤ 10⁹).

Các số trên mỗi dòng được cách nhau bởi dấu cách.

Output: Ghi ra môt số nguyên duy nhất là kết quả cưa bài toán theo modulo 10⁹ + 7.

Chú ý:

• Subtask 1 (1 điểm): n ≤ 5.10³;
• Subtask 2 (3 điểm): n ≤ 5.10⁴, S = 0;
• Subtask 3 (3 điểm): n ≤ 5.10⁴.

Example

Input:
4 3
1 2 3 4

Output:
143