题目描述

小$Z$特别喜欢吃月饼！所以他经常在家附近的集市买月饼，碰巧这个集市里面卖的都是五仁月饼。集市里有 $n$ 家店铺，编号为$1\sim n$，第 $i$ 家店铺的月饼的库存量为 $a_i$，即在第 $i$ 家店铺中小$Z$可以选择购买 $0 \sim a_i$个月饼（买0个即是不买）。

定义小$Z$的快乐值为在所有店铺买的月饼的数量的异或和，也就是说如果小$Z$在第 $i$ 个店铺购买了 $b_i$个月饼, 那么他的快乐值就等于 $\oplus_{i=1}^n b_i，即b_1 \oplus b_2 \oplus \cdots \oplus b_n$其中$\oplus$表示按位异或运算。

有一天，他去集市时突然想到了一个问题：如果只在编号为$[l,r]$的这一段店铺区间中买月饼，有多少购买方法使得自己的快乐值为 $s$ ？这个问题很难回答…… 因为小$Z$数学不好。于是，他只好求助聪明的你，来解决这个问题，由于这个答案可能很大，故输出时对 $10^9 + 7$取模。

输入描述

第一行两个正整数 $n,q(1\le n \le 10^3, 1\le q \le 10^5)$，表示分别店铺个数以及询问次数。

第二行 $n$ 个正整数 $a_i(1\le a_i \le 10^3)$，第$i$个整数表示第 $i$ 家店铺中的月饼的库存量。

后面 $q$ 行，每行三个整数 $l, r,s(1 \le l \le r \le n, 0\le s \le 10^3)$分别代表询问的一段店铺区间以及快乐值。

输出描述

输出 $q$ 行，每行一个整数，依次表示询问对应的答案，答案对 $10^9 + 7$取模。

样例输入

6 6
1 1 4 5 1 4
1 1 0
1 2 0
1 3 0
1 4 0
1 5 0
1 6 0

样例输出

1
2
4
20
40
168