As you know, the greatest combat between Quentin Coldwater and Julius Novachrono is going to take place this year in RUET (Riddle's University of Enhancement and Transfiguration). Everyone is eagerly waiting for this combat. The time is very short for taking preparation for the combat. Quentin is very serious because this is the last chance for him to win. So he wants to take his best preparation.
He has a book of spell of N pages, called the Diary of Tom Riddle. The pages are numbered from 1 to N. Each page of the diary contains a single magical instruction. And each magical instruction has a magical value.
Quentin can create a spell by using a series of instructions from the diary.
To create a spell, he should start reading the diary from any i-th page and follow the instructions up to any j-th (i ≤ j) page as he wishes.
For example, if the diary has 10 pages then possible page indices chosen for creating spell can be from page (1 to 2) or (2 to 5) or (3 to 3) or (1 to 10) etc.
Each magic instruction of the diary is unique, even though the magical values might not be. Two spells are different if at least one magic instruction differs between them. Quentin wants to create unique spells only, because if he creates the same spell twice then both spells will destroy each other.
For example, a spell created by using instructions from page (1 to 2) is unique. So if he again uses the same instructions (from page 1 to 2) then both spells will destroy each other.
Quentin won't do that because that will weaken his power.
The strength of a created spell is the product of the magical values of the selected instructions.
But if he chooses less than K instructions to create a spell then the spell will be too weak to be active.
And if he misses any instruction in between his chosen i-th page and the j-th page then the spell will be defective and will not work properly.
For example, if he starts from page 1 to page 5, then he can not skip any instructions in between page 1 to 5.
As Quentin is very serious and wants to be powerful enough, he wants to create maximum number of correct and active magic spells for the combat. As he is busy in making spells, he asks your help to calculate the total strength of the magical spells he can create for the combat. Total strength will be the summation of strengths of all the created spells.
As the answer can be very large, you will have to print the answer modulo 109+7
Input
The first line of input contains two integer N (1 ≤ N ≤ 2∗105) and K (1 ≤ K ≤ N) denoting the number of pages of magic books and the minimum number of instructions required to create a spell to be strong enough respectively.
Each of the next N lines contains a 32 bit integer. The i-th integer denotes the magical value of the instruction of i-th page from the diary.
Output
You will have to print a single integer denoting the total strength of the spells created by Quentin if he creates maximum number of spells.
As the answer can be very large, you will have to print the answer modulo 109+7
Samples
| Input | Output |
|---|---|
4 2 2 3 5 7 | 401 |
| Input | Output |
|---|---|
5 3 2 6 1 4 3 | 312 |
