Average Stamp Benefit

You are given n stamp slots. Each slot i contains an infinite number of stamps, and every stamp in slot i has a value \(a_{i}\).

A mechanical arm is used to pick stamps. In each pick, the arm grabs the stamp from the slot directly beneath its current position. After grabbing a stamp, the arm either stays in the same slot or moves to the right (it can move any number of slots to the right in one move). Initially, the arm can start at any slot. However, at all times the arm must be positioned at one of the stamp slots.

The arm performs \(k\) picks. After \(k\) picks, the total benefit is defined as the product of the values of the picked stamps. Assuming that every allowed operation is chosen uniformly at random, compute the expected benefit. Since the answer may not be an integer, output it modulo \(19260817\).

inputFormat

The first line contains two integers \(n\) and \(k\) (for example, \(1 \le n, k \le 10^3\)).

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)).

outputFormat

Output a single integer representing the expected benefit modulo \(19260817\).

sample

3 2
2 3 5

10