题目描述Description

For a string s₁, s₂, …, s_n, Bobo denotes the number of its distinct substrings as f(s₁, s₂, …, s_n). He also defines h(c) = f(s₁, s₂, …, s_n, c) − f(s₁, s₂, …, s_n) for character c.

Given a string s₁, s₂, …, 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 ⊕ 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₁, s₂, …, s_n.

• 1 ≤ n, m ≤ 10⁶
• 1 ≤ s_i ≤ m
• The sum of n does not exceed 5 × 10⁶.
• The sum of m does not exceed 5 × 10⁶.

输出格式Output

For each test case, print an integer which denotes the result.

样例Sample

提示Hint

For the second test case, h(1) = h(2) = 2, h(3) = 3.

出题Author

ftiasch

来源Source