{"raw_statement":[{"iden":"statement","content":"David is a young child. He likes playing combinatorial games, for example, the Nim game. He is just an amateur but he is sophisticated with game theory. This time he has prepared a problem for you.\n\nGiven integers N, L, R and K, you are asked to count in how many ways one can arrange an integer array of length N such that all its elements are ranged from L to R (inclusive) and the bitwise exclusive-OR of them equals to K. To avoid calculations of huge integers, print the number of ways in modulo (109 + 7).\n\nIn addition, David would like you to answer with several integers K in order to ensure your solution is completely correct.\n\nThe first line contains one integer T, indicating the number of test cases.\n\nThe following lines describe all the test cases. For each test case:\n\nThe first line contains four space-separated integers N, L, R and Q, indicating there are Q queries with the same N, L, R but different K.\n\nThe second line contains Q space-separated integers, indicating several integers K.\n\n1 ≤ T ≤ 1000, 1 ≤ N ≤ 109, 0 ≤ L ≤ R < 230, 1 ≤ Q ≤ 100, 0 ≤ K < 230.\n\nIt is guaranteed that no more than 100 test cases do not satisfy 1 ≤ N ≤ 15, 0 ≤ L, R, K < 215.\n\nFor each query, print the answer modulo (109 + 7) in one line.\n\nIn the first sample, there are two ways to select one number 3 and one number 4 such that the exclusive-OR of them is 7.\n\nIn the second sample, there are three ways to select one number 3 and two numbers 4 and one way to select three numbers 3 such that the exclusive-OR of them is 3.\n\n"},{"iden":"input","content":"The first line contains one integer T, indicating the number of test cases.The following lines describe all the test cases. For each test case:The first line contains four space-separated integers N, L, R and Q, indicating there are Q queries with the same N, L, R but different K.The second line contains Q space-separated integers, indicating several integers K.1 ≤ T ≤ 1000, 1 ≤ N ≤ 109, 0 ≤ L ≤ R < 230, 1 ≤ Q ≤ 100, 0 ≤ K < 230.It is guaranteed that no more than 100 test cases do not satisfy 1 ≤ N ≤ 15, 0 ≤ L, R, K < 215."},{"iden":"output","content":"For each query, print the answer modulo (109 + 7) in one line."},{"iden":"note","content":"In the first sample, there are two ways to select one number 3 and one number 4 such that the exclusive-OR of them is 7.In the second sample, there are three ways to select one number 3 and two numbers 4 and one way to select three numbers 3 such that the exclusive-OR of them is 3."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ N \\in \\mathbb{Z} $, $ L, R \\in \\mathbb{Z} $, $ Q \\in \\mathbb{Z} $ be parameters.  \n- Let $ S = \\{ x \\in \\mathbb{Z} \\mid L \\le x \\le R \\} $ be the set of allowed integers.  \n- Let $ K_1, K_2, \\dots, K_Q \\in \\mathbb{Z} $ be the query values.  \n\n**Constraints**  \n1. $ 1 \\le T \\le 1000 $  \n2. $ 1 \\le N \\le 10^9 $  \n3. $ 0 \\le L \\le R < 2^{30} $  \n4. $ 1 \\le Q \\le 100 $  \n5. $ 0 \\le K_j < 2^{30} $ for all $ j \\in \\{1, \\dots, Q\\} $  \n6. At most 100 test cases have $ N \\le 15 $ and $ L, R, K_j < 2^{15} $  \n\n**Objective**  \nFor each test case and each query $ K_j $, compute:  \n$$\n\\left| \\left\\{ (x_1, \\dots, x_N) \\in S^N \\mid x_1 \\oplus x_2 \\oplus \\cdots \\oplus x_N = K_j \\right\\} \\right| \\mod (10^9 + 7)\n$$","simple_statement":"Count the number of ways to choose N integers between L and R (inclusive) such that their XOR equals K, modulo 10^9+7. Answer Q queries for different K values with the same N, L, R.","has_page_source":false}