For a string $s_1, s_2, \dots, s_n$, Bobo denotes the number of its distinct substrings as $f(s_1, s_2, \dots, s_n)$. He also defines defines $h(c) = f(s_1, s_2, \dots, s_n, c) - f(s_1, s_2, \dots, s_n)$ for character $c$.
Given a string $s_1, s_2, \dots, s_n$ and $m$, find the value of $\bigoplus_{c = 1}^{m}\left(h(c) \cdot 3^c \bmod (10^9+7)\right)$.
Note that $\oplus$ denotes the bitwise exclusive-or (XOR).
Input
The input consists of several test cases and is terminated by end-of-file.
The first line of each test case contains two integers $n$ and $m$.
The second line contains $n$ integers $s_1, s_2, \dots, s_n$.
- $1 \leq n, m \leq 10^6$
- $1 \leq s_i \leq m$
- The sum of $n$, and the sum of $m$ do not exceed $5 \times 10^6$.
Output
For each test case, print an integer which denotes the result.
Sample Input
3 2 1 1 2 2 3 1 2 1 1000000 1
Sample Output
18 69 317072014
Note
For the second test case, $h(1) = h(2) = 2, h(3) = 3$.