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.

ftiasch