Background

As a Roguelike game, TODR features a rich equipment system. Each piece of equipment has a unique appearance and stunning effects, with hundreds of seals each with their own effects, and a complex system of synthesis, decomposition, and fusion. These elements together create a highly engaging gameplay experience.

Now that your equipment has reached its maximum level, it needs to be fused with other equipment to continue growing. Of course, you need Nitori Kawashiro to extract the seals from your original equipment for synthesis with the new equipment.

Problem Description

Given that the original equipment has \( n \) seal slots, each slot contains an infinite number of a certain type of seal, with the value of the seal in the \( i \)-th slot being \( a_i \).

Nitori Kawashiro will use a robotic arm to extract seals from the slots. Each extraction involves the arm reaching down to grab a seal from the slot directly below it, and then moving right or staying in place (if moving, it can move any number of slots). The initial position of the arm is arbitrary, but at any time, the arm must be positioned over a seal slot.

Nitori Kawashiro will perform \( k \) extractions, and the total gain you receive after the extractions is equal to the product of the values of the \( k \) seals extracted.

Assuming that all operations performed by Nitori Kawashiro are random, what is the average value of the gain you can obtain?

Since the answer may not be an integer, you only need to output the result modulo \( 19260817 \).

Input Format

The first line contains two integers \( n \) and \( k \), representing the number of seal slots and the number of extractions, respectively.

The second line contains \( n \) positive integers \( a_i \), representing the value of the seals in each slot.

Output Format

A single integer representing the average value of the gain after \( k \) extractions, modulo \( 19260817 \).

Sample Input and Output

Sample Input #1

3 2
3 1 2

Sample Output #1

16050685

Sample Input #2

6 3
1 1 4 5 1 4

Sample Output #2

16509294

Notes

Sample 1 Explanation:

The robotic arm can start above any of the three slots.

The possible sequences of extraction positions are \((1,1), (1,2), (1,3), (2,2), (2,3), (3,3)\), with gains of \(9, 3, 6, 1, 2, 4\) respectively. The average value is \(\frac{25}{6}\), which modulo \( 19260817 \) equals \( 16050685 \).

Data Range:

\( a_i < 19260817 \)

见题面 Input 部分

见题面 Output 部分