No.1102 Remnants
eSeF
37zigenProblem Statement
You have a sequence $A=(A_1,\dots ,A_N)$ of length $N$ consisting of positive integers.
You perform the following operation on it $K$ times.
- Let $B=(B_1,\dots ,B_M)$ be the sequence at the time of the operation.
Freely choose integers $l,\ r$ satisfying $1\le l\le r\le M$, and replace the sequence you have with the contiguous subsequence $(B_l,B_{l+1},\dots ,B_r)$. (Indices are renumbered starting from 1.)
The score of a series of $K$ operations is defined as the sum of the elements of the sequence after all operations have finished.
Find the score for every possible operation procedure, and print the total of these scores modulo $10^9+7$.
Two operation procedures are considered different if there exists a positive integer $i$ such that
the pairs of integers $(l,\ r)$ chosen in the $i$-th operation differ.
Input
$N\ \ K$ $A_1 \ \ \dots \ \ A_N$
[Constraints]
- $1\le N\le 2\times 10^5$
- $0\le K\le 10^8$
- $1\le A_i\le 10^9$
- All inputs are integers.
Output
Print the answer.
Sample
Sample 1
Input
2 2 3 4
Output
21
After the first operation, the sequence becomes one of $(3,4),\ (3),\ (4)$.
In the second operation, $(3,4)$ changes into one of $(3,4),\ (3),\ (4)$.
$(3)$ changes into $(3)$, and $(4)$ changes into $(4)$.
Therefore, the total score is $7+3+4+3+4=21$.
Sample 2
Input
4 0 1 2 3 4
Output
10
No operations are performed, so there is only one operation procedure, and the total score is $10$.
Sample 3
Input
5 100000000 1000000000 999999999 888888888 777777777 666666666
Output
870870837
The total can be very large, so print it modulo $10^9+7$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。