Có \(n\) món quà, món quà thứ \(i\) có giá trị là \(A_i\).

A sẽ tặng \(K\) món quà cho B.

Mỗi cách A tặng quà cho B có thể được biểu diễn bởi tập các chỉ số \(i_1, i_2, \ldots, i_K ~ (1 \leq i_1 < i_2 < \ldots < i_K \leq n)\). Và giá trị của cách tặng quà này là \(\sum_{j=1}^{K} A_{i_j}\).

Hãy tính tổng giá trị của tất cả các cách tặng quà, chia dư cho \((10^9 + 7)\).

Input

• Dòng đầu tiên chứa hai số \(n, K\) \((1 \leq K \leq n \leq 2 \times 10^5)\).
• Dòng thứ hai chứa \(n\) số nguyên, số thứ \(i\) là \(A_i\) \((|A_i| \leq 20242024)\).

Output

• Một dòng duy nhất chứa tổng giá trị của các cách tặng quà, chia dư cho \((10^9 + 7)\).

Scoring

• Subtask 1 (\(10\%\) số điểm): \(n \leq 10\).
• Subtask 2 (\(40\%\) số điểm): \(n \leq 1000\).
• Subtask 3 (\(50\%\) số điểm): \(n \leq 2 \times 10^5\).

Example

3 2
1 2 3

12