对于字符串 $s_1, s_2, \dots, s_n$，Bobo 将其不同子串的数量记为 $f(s_1, s_2, \dots, s_n)$。他还定义了对于字符 $c$ 的函数 $h(c) = f(s_1, s_2, \dots, s_n, c) - f(s_1, s_2, \dots, s_n)$。

给定字符串 $s_1, s_2, \dots, s_n$ 和 $m$，求下式的值： $\bigoplus_{c = 1}^{m}\left(h(c) \cdot 3^c \bmod (10^9+7)\right)$

其中 $\oplus$ 表示按位异或（XOR）。

输入格式

输入包含多组测试数据，以文件结束符（EOF）终止。

每组测试数据的第一行包含两个整数 $n$ 和 $m$。

第二行包含 $n$ 个整数 $s_1, s_2, \dots, s_n$。

• $1 \leq n, m \leq 10^6$
• $1 \leq s_i \leq m$
• $n$ 的总和与 $m$ 的总和均不超过 $5 \times 10^6$。

输出格式

对于每组测试数据，输出一个整数表示结果。

样例

样例输入 1

3 2
1 1 2
2 3
1 2
1 1000000
1

样例输出 1

18
69
317072014

说明

对于第二组测试数据，$h(1) = h(2) = 2, h(3) = 3$。