Farmer John đang cố sản xuất loại sữa OohMoo Milk nổi tiếng thế giới của mình để bán kiếm lời. Ông có \(N\) (\(1\leq N\leq 10^5\)) chai cần đổ đầy. Ban đầu, mỗi chai chứa một lượng sữa \(m_i\) (\(0\leq m_i\leq 10^9\)). Mỗi ngày, ông chọn \(A\) (\(1\le A\le N\)) chai và đổ thêm một đơn vị sữa vào mỗi chai.

Không may, Farmer Nhoj, đối thủ của Farmer John trong ngành kinh doanh OohMoo Milk, biết quy trình sản xuất của Farmer John và có kế hoạch kìm hãm việc kinh doanh của ông. Mỗi ngày, sau khi Farmer John đổ sữa vào \(A\) chai, Farmer Nhoj sẽ lén lấy đi một đơn vị sữa từ mỗi chai trong số \(B\) (\(0\le B<A\)) chai khác nhau đang không rỗng. Để tránh bị phát hiện, Farmer Nhoj chọn \(B\) nhỏ hơn hẳn \(A\), khiến Farmer John ít có khả năng phát hiện ra hắn hơn.

Sau \(D\) (\(1\leq D\leq 10^9\)) ngày, Farmer John sẽ bán OohMoo Milk. Nếu một chai có \(M\) đơn vị sữa, nó sẽ được bán với giá \(M^2\) moonie.

Gọi \(P\) là lợi nhuận duy nhất sao cho FJ có thể đảm bảo kiếm được ít nhất \(P\) bất kể FN hành động thế nào, và FN có thể đảm bảo FJ kiếm được nhiều nhất \(P\) bất kể FJ hành động thế nào. Hãy in \(P\) modulo \(10^9+7\).

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(D\), trong đó \(N\) là số chai và \(D\) là số ngày.

Dòng thứ hai chứa \(A\) và \(B\), lần lượt là số đơn vị sữa Farmer John thêm vào và Farmer Nhoj lấy đi.

Dòng thứ ba chứa \(N\) số nguyên \(m_i\) cách nhau bởi dấu cách, biểu thị lượng sữa ban đầu trong mỗi chai.

Dữ liệu ra

In ra giá trị \(P\) modulo \(10^9+7\).

Ví dụ

5 4
4 2
4 10 8 10 10

546

10 5
5 1
1 2 3 4 5 6 7 8 9 10

777

5 1000000000
3 1
0 1 2 3 4

10

Phân nhóm

• Dữ liệu 4–6: \(N,D\le 1000\).
• Dữ liệu 7–10: \(D\le 10^6\).
• Dữ liệu 11–20: Không có ràng buộc bổ sung.

Đề bài: Suhas Nagar.

Nguồn

USACO 2025 US Open Contest, Gold — OohMoo Milk: https://usaco.org/index.php?page=viewproblem2&cpid=1523