{"raw_statement":[{"iden":"statement","content":"Ehab has an array _a_ of _n_ integers. He likes the [bitwise-xor operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) and he likes to bother Mahmoud so he came up with a problem. He gave Mahmoud _q_ queries. In each of them, he gave Mahmoud 2 integers _l_ and _x_, and asked him to find the number of subsequences of the first _l_ elements of the array such that their bitwise-xor sum is _x_. Can you help Mahmoud answer the queries?\n\nA subsequence can contain elements that are not neighboring."},{"iden":"input","content":"The first line contains integers _n_ and _q_ (1 ≤ _n_, _q_ ≤ 105), the number of elements in the array and the number of queries.\n\nThe next line contains _n_ integers _a_1, _a_2, ..., _a__n_ (0 ≤ _a__i_ < 220), the elements of the array.\n\nThe next _q_ lines, each contains integers _l_ and _x_ (1 ≤ _l_ ≤ _n_, 0 ≤ _x_ < 220), representing the queries."},{"iden":"output","content":"For each query, output its answer modulo 109 + 7 in a newline."},{"iden":"examples","content":"Input\n\n5 5\n0 1 2 3 4\n4 3\n2 0\n3 7\n5 7\n5 8\n\nOutput\n\n4\n2\n0\n4\n0\n\nInput\n\n3 2\n1 1 1\n3 1\n2 0\n\nOutput\n\n4\n2"},{"iden":"note","content":"The bitwise-xor sum of the empty set is 0 and the bitwise-xor sum of a set containing one element is that element itself."}],"translated_statement":[{"iden":"statement","content":"Ehab 有一个包含 $n$ 个整数的数组 $a$。他喜欢按位异或运算，并且喜欢打扰 Mahmoud，因此他想出了一个问题。他给了 Mahmoud $q$ 个查询。在每个查询中，他给 Mahmoud 两个整数 $l$ 和 $x$，并要求他找出数组前 $l$ 个元素的子序列中，其按位异或和等于 $x$ 的子序列数量。你能帮助 Mahmoud 回答这些查询吗？\n\n子序列可以包含不相邻的元素。\n\n第一行包含整数 $n$ 和 $q$ $ (1 ≤ n, q ≤ 10^5) $，分别是数组中元素的数量和查询的数量。\n\n下一行包含 $n$ 个整数 $a_1$, $a_2$, $\\dots$, $a_n$ $ (0 ≤ a_i < 2^{20}) $，表示数组的元素。\n\n接下来的 $q$ 行，每行包含两个整数 $l$ 和 $x$ $ (1 ≤ l ≤ n, 0 ≤ x < 2^{20}) $，表示一个查询。\n\n对于每个查询，请在一行中输出其答案对 $10^9 + 7$ 取模的结果。\n\n空集的按位异或和为 0，仅包含一个元素的集合的按位异或和即为该元素本身。"},{"iden":"input","content":"第一行包含整数 $n$ 和 $q$ $ (1 ≤ n, q ≤ 10^5) $，分别是数组中元素的数量和查询的数量。下一行包含 $n$ 个整数 $a_1$, $a_2$, $\\dots$, $a_n$ $ (0 ≤ a_i < 2^{20}) $，表示数组的元素。接下来的 $q$ 行，每行包含两个整数 $l$ 和 $x$ $ (1 ≤ l ≤ n, 0 ≤ x < 2^{20}) $，表示一个查询。"},{"iden":"output","content":"对于每个查询，请在一行中输出其答案对 $10^9 + 7$ 取模的结果。"},{"iden":"examples","content":"输入\n5 5\n0 1 2 3 4\n4 3\n2 0\n3 7\n5 7\n5 8\n输出\n4\n2\n0\n4\n0\n\n输入\n3 2\n1 1 1\n3 1\n2 0\n输出\n4\n2"},{"iden":"note","content":"空集的按位异或和为 0，仅包含一个元素的集合的按位异或和即为该元素本身。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, q \\in \\mathbb{Z}^+ $ denote the length of the array and the number of queries.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers with $ a_i \\in \\{0, 1, \\dots, 2^{20} - 1\\} $.  \nFor each query $ j \\in \\{1, \\dots, q\\} $, let $ l_j \\in \\{1, \\dots, n\\} $ and $ x_j \\in \\{0, 1, \\dots, 2^{20} - 1\\} $ be given.\n\n**Constraints**  \n1. $ 1 \\leq n, q \\leq 10^5 $  \n2. $ 0 \\leq a_i < 2^{20} $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. $ 1 \\leq l_j \\leq n $, $ 0 \\leq x_j < 2^{20} $ for all $ j \\in \\{1, \\dots, q\\} $\n\n**Objective**  \nFor each query $ j $, compute the number of subsequences of the prefix $ A_{l_j} = (a_1, a_2, \\dots, a_{l_j}) $ whose bitwise XOR sum equals $ x_j $.  \n\nLet $ S \\subseteq \\{1, 2, \\dots, l_j\\} $ be a subset of indices. Define the XOR sum of the subsequence indexed by $ S $ as:  \n$$\n\\bigoplus_{i \\in S} a_i\n$$  \nwhere $ \\bigoplus $ denotes bitwise XOR, and the XOR over the empty set is 0.  \n\nLet $ f_j = \\left| \\left\\{ S \\subseteq \\{1, \\dots, l_j\\} \\ \\middle|\\ \\bigoplus_{i \\in S} a_i = x_j \\right\\} \\right| $.  \nOutput $ f_j \\mod (10^9 + 7) $ for each query $ j $.","simple_statement":null,"has_page_source":false}