CSG-CPC
Online Judge

1071 : Distinct Substrings

         Time Limit: 5 Sec     Memory Limit: 512 Mb     Submitted: 59     Solved: 18    

Description

For a string s1, s2, …, sn, Bobo denotes the number of its distinct substrings as f(s1, s2, …, sn). He also defines h(c) = f(s1, s2, …, sn, c) − f(s1, s2, …, sn) for character c.

Given a string s1, s2, …, sn 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 s1, s2, …, sn.

  • 1 ≤ n, m ≤ 106
  • 1 ≤ si ≤ m
  • The sum of n does not exceed 5 × 106.
  • The sum of m does not exceed 5 × 106.

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.

Author

ftiasch