题目描述

Blice 和阿强巴是好朋友。

但萌萌哒 Blice 不擅长数学，所以阿强巴给了她一些奶牛做联系。

阿强巴有 $n$ 头奶牛，他需要把这些奶牛划分成若干组，每组种至少有一头奶牛，当 $n=5$ 时，方案 $\text{{1,1,3}}$ 和 $\text{{1,3,1}}$ 是相同的方案，而方案 $\text{{1,1,3}}$ 和 $\text{{2,3}}$ 则是不同的方案。

现在阿强巴想直到有多少种不同的划分方案……不不不，这对于 Blice 时在太简单了，所以阿强巴要出的再难一点。

因此阿强巴又定义了一个二元函数 $F(x,y)$，设一个划分方案数列 $p$，长度为 $m$（下标从 $1$ 开始），那么对于该划分方案来说，它的价值就是 $\sum\limits_{i=1}^m\sum\limits_{j=i+1}^mF(p_i,p_j)$，显然当 $m=1$ 时，这个划分方案的价值为 $0$。

（$F(x,y)$ 的具体含义会在后面给出）

现在阿强巴想直到所有不同的划分方案的价值总和……不不不，这对于 Blice 时在太简单了，所以阿强巴要出的再难一点。

因此阿强巴又生成了一个数列 $a$，长度为 $k$（下标从 $0$ 开始），他重新定义了划分方案的价值，即 $\sum\limits_{i=1}^m\sum\limits_{j=i+1}^ma_{F(p_i,p_j)\bmod k}$，这里的 $F(p_i,p_j)\bmod p$ 是数列下标。

Blice 终于不会做了，你能帮帮她吗？

由于答案可能很大，你只需要数处模 $10^9+7$ 意义下的答案。

输入格式

共有三种 $F(x,y)$ 的定义，用在第一行输入的一个整数 $type$ 来表示
当 $type = 1$，$F(x,y)=1$；
当 $type = 2$，$F(x,y)=\gcd(x,y)$；
当 $type = 3$，$F(x,y)=x^y+y^x+x\operatorname{xor}y$。
第二行是两个整数 $n,k$，表示奶牛的数量和数列 $a$ 的长度。
第三行又 $k$ 个整数，第 $i$ 个整数表示 $a_{i-1}$。

输出格式

仅一行，表示最终的答案。

1
3 3
0 1 2

4

2
5 4
4 1 5 2

31

3
7 5
12 11 45 6 2

7346

数据规模与约定

对于 $100\%$ 的数据，满足 $n\le 2\times 10^3$，$type\in \text{{1,2,3}}$，$k\le 10^5$，$a_i\in[0,10^7]$ 且为整数。