暂无测试数据。

Description

维克多词汇书中有\(n\)个单词，其中第\(i\)个单词的难度为\(a_i\)，那么整本书可以看做一个长度为\(n\)的序列，序列中第\(i\)个数为\(a_i\)。
现在，需要你计算两个答案：

1,一个区间的权值是左端点单词难度和右端点单词难度的异或值乘以区间中所有单词难度的最大值，求所有区间的权值之和。
即 \[ ans_1 = \sum_{l=1}^{n} \sum_{r=l}^{n} (a_l \; xor \;a_r) \times max \{ a_i | l \leq i \leq r \} \]
2,如果一个区间满足左端点单词难度和右端点单词难度的异或值大于区间中所有单词难度的最大值，那么这个区间的权值为区间中所有单词难度的最大值，否则为0。

即 \[ ans_2 = \sum_{l=1}^{n} \sum_{r=l}^{n} [(a_l \; xor \;a_r) > max \{ a_i | l \leq i \leq r \} ] \times max \{ a_i | l \leq i \leq r \}\]

其中，若判断条件\(w\)为真，则[w]=1，否则[w]=0。
由于答案可能较大，\(ans_1\)与\(ans_2\)都需要对\(10^9+7\)取模。

Format

Input

第一行有\( 3 \)个整数 \(n, opt\)，\(opt\)的意义将在输出格式中提到。
第二行有\( n \)个整数，第\( i \)个整数表示\(a_i\)。

Output

若\( opt=1 \)，输出一行一个整数表示\(ans_1\)。
若\( opt=2 \)，输出一行一个整数表示\(ans_2\)。
若\( opt=3 \)，输出两行，第一行一个整数\(ans_1\)，第二行一个整数\(ans_2\)。

Sample 1

Input

3 3
6 1 3

Output

78
6

Limitation

1s, 512MiB for each test case.

Hint

更多输入输出样例请见选手下发文件夹。

数据范围与约定

对于所有数据，\(1 ≤ n ≤ 10^5, 1 ≤ opt ≤ 3, 0 ≤ a_i ≤ 10^6\)。

测试点编号	n	opt	特殊性质
1~4	\(≤10^3\)	\(=3\)	无
5~6	\(=99996\)	\(=1\)	对于 \(1 ≤ i < n, a_i < a_{i+1}\)
7~8	\(=99996\)	\(=2\)	对于 \(1 ≤ i < n, a_i < a_{i+1}\)
9~10	\(=99997\)	\(=1\)	对于 \(1 ≤ i ≤ n, 0 ≤ a_i ≤ 1\)
11~12	\(=99997\)	\(=2\)	对于 \(1 ≤ i ≤ n, 0 ≤ a_i ≤ 1\)
13~16	\(=99998\)	\(=1\)	对于 \( 1 ≤ i ≤ n, 0 ≤ a_i <10 \)
17~18	\(=99999\)	\(=3\)	\(a\_i\)互不相同
19~20	\(=10^5\)	\(=3\)	无

Source

CSP2019第二轮测试模拟题（一）