Magical Transformation

You are given a sequence of integers and a magical exponent m. Your task is to compute the sum of each element raised to the power of m modulo \(10^9+7\). Formally, given a sequence \(a_1, a_2, \dots, a_n\), compute

\[ S = \left(\sum_{i=1}^{n} a_i^m\right) \bmod (10^9+7) \]

Input Example: For instance, if \(n=3\), the sequence is [1,2,3] and \(m=2\), then the answer is \(1^2 + 2^2 + 3^2 = 1+4+9=14\).

inputFormat

The input is given in two lines:

• The first line contains two space-separated integers \(n\) and \(m\), where \(n\) is the number of elements in the sequence and \(m\) is the magical exponent.
• The second line contains \(n\) space-separated integers representing the sequence.

outputFormat

Output a single integer representing the sum \(S = \left(\sum_{i=1}^{n} a_i^m\right) \bmod (10^9+7)\).

3 2
1 2 3

14