Expected Power of Combo Moves

Given a workout routine consisting of \(N\) moves where each move is chosen independently and uniformly from \(k\) distinct moves. The \(i\)th move has a power value \(a_i\) for \(1 \le i \le k\). In addition, if a move of type \(i\) is immediately followed by a move of type \(i+1\) (and a move of type \(k\) is considered followed by a move of type \(1\)), an extra bonus of \(a_i + a_{i+1}\) is added. The total power of a routine is the sum of the individual move powers together with the bonus powers for every valid consecutive pair.

The total power \(P\) for a sequence \(m_1, m_2, \dots, m_N\) is given by:

[ P = \sum_{j=1}^{N}a_{m_j} + \sum_{j=1}^{N-1}B(m_j, m_{j+1}) ]

where \[ B(m_j, m_{j+1}) = \begin{cases} a_{m_j} + a_{m_{j+1]}, & \text{if } m_{j+1} \equiv m_j+1 \; (\text{mod } k) \\ 0, & \text{otherwise} \end{cases} \]

Assuming each move is chosen uniformly at random, compute the expected total power of the routine modulo \(19491001\). Note that the effect of division must be handled via modular inverses.

inputFormat

The first line contains two integers \(k\) and \(N\) (with \(1 \le k, N \le 10^9\)).

The second line contains \(k\) space-separated integers \(a_1, a_2, \dots, a_k\) (\(1 \le a_i \le 10^9\)).

outputFormat

Output a single integer: the expected total power modulo \(19491001\).

sample

3 5
1 2 3

?