1071 : Distinct Substrings

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

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

18
69
317072014

Hint

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

Source

Author

ftiasch