{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eDavid 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.\u003cbr\u003eGiven 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 $(10^9 + 7)$.\u003cbr\u003eIn addition, David would like you to answer with several integers $K$ in order to ensure your solution is completely correct.\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains one integer $T$, indicating the number of test cases.\u003cbr\u003eThe following lines describe all the test cases. For each test case:\u003cbr\u003eThe 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$.\u003cbr\u003eThe second line contains $Q$ space-separated integers, indicating several integers $K$.\u003cbr\u003e$1 \\leq T \\leq 1000$, $1 \\leq N \\leq 10^9$, $0 \\leq L \\leq R \u0026lt; 2^{30}$, $1 \\leq Q \\leq 100$, $0 \\leq K \u0026lt; 2^{30}$.\u003cbr\u003eIt is guaranteed that no more than $100$ test cases do not satisfy $1 \\leq N \\leq 15$, $0 \\leq L, R, K \u0026lt; 2^{15}$.\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each query, print the answer modulo $(10^9 + 7)$ in one line.\u003cbr\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n2 3 4 2\r\n0 7\r\n3 3 4 2\r\n3 4\r\n5 5 7 4\r\n5 6 7 8\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n2\r\n4\r\n4\r\n61\r\n61\r\n61\r\n0\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003eIn 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.\u003cbr\u003eIn 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.\u003cbr\u003e"}}]}