Distinct Substrings

题号：NC53382
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
Special Judge, 64bit IO Format: %lld

题目描述

For a string $s_1, s_2, \dots, s_n$ , Bobo denotes the number of its distinct substrings as $f(s_1, s_2, \dots, s_n)$ . He also defines defines $h(c) = f(s_1, s_2, \dots, s_n, c) - f(s_1, s_2, \dots, s_n)$ for character c.
Given a string $s_1, s_2, \dots, 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 $\oplus$ denotes the bitwise exclusive-or (XOR).

输入描述:

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 .

* 
* 
* The sum of n, and the sum of m do not exceed .

输出描述:

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

示例1

输入

复制

输出

复制

18
69
317072014

备注:

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