{"raw_statement":[{"iden":"statement","content":"Alice and Bob decided to play the following game on $n$ piles of stones where the $i^(t h) (1 <= i <= n)$ pile contains $p_i$ stones, with Alice starting first :\n\nThe player who cannot make a move loses. Note that both Alice and Bob are intelligent, so they always play optimally.\n\nNow your task is to *count* the number of permutations$\"\"^dagger$ $p$ of length $n$ such that the number of pairs ($l, r$)($1 <= l <= r <= n$), where Alice will win if both players play the game on piles $l, l + 1,..., r -1, r$, is *maximum* possible.\n\n$\"\"^dagger$ A permutation is an array of length $n$, where each number from $1$ to $n$ appears exactly once.\n\nEach test contains multiple test cases. The first line contains the number of test cases $t$ ($1 <= t <= 10000$). The description of the test cases follows.\n\nThe first line of each test case contains a single integer $n$ ($1 <= n <= 3 dot.op 10^5$) — the number of piles.\n\nIt is guaranteed that the sum of $n$ over all test cases doesn't exceed $3 dot.op 10^5$.\n\nFor each test case, print a single integer — the required answer modulo $10^9 + 7$.\n\n"},{"iden":"input","content":"Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 <= t <= 10000$). The description of the test cases follows.The first line of each test case contains a single integer $n$ ($1 <= n <= 3 dot.op 10^5$) — the number of piles.It is guaranteed that the sum of $n$ over all test cases doesn't exceed $3 dot.op 10^5$."},{"iden":"output","content":"For each test case, print a single integer — the required answer modulo $10^9 + 7$."}],"translated_statement":[{"iden":"statement","content":"*这是该问题的困难版本。唯一的区别是存在第三个限制*。\n\n给定两个整数 $n$ 和 $x$。构造一个长度为 $2 n$ 的排列 $p$，使其满足：\n\n如果没有解，则输出 $-1$。\n\n输入的第一行包含一个整数 $t (1 lt.eq t lt.eq 10^5)$，表示测试用例的数量。\n\n每个测试用例占一行。\n\n每个测试用例的唯一一行包含两个整数 $n (2 lt.eq n lt.eq 10^5), x (1 lt.eq x lt.eq 2 n)$。所有测试用例的 $n$ 之和不超过 $10^5$。\n\n对于每个测试用例，在新行上输出一个满足上述限制的长度为 $2 n$ 的排列。如果没有解，则输出 $-1$。"},{"iden":"input","content":"输入的第一行包含一个整数 $t (1 lt.eq t lt.eq 10^5)$，表示测试用例的数量。每个测试用例占一行。每个测试用例的唯一一行包含两个整数 $n (2 lt.eq n lt.eq 10^5), x (1 lt.eq x lt.eq 2 n)$。所有测试用例的 $n$ 之和不超过 $10^5$。"},{"iden":"output","content":"对于每个测试用例，在新行上输出一个满足上述限制的长度为 $2 n$ 的排列。如果没有解，则输出 $-1$。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ t \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, t\\} $, let $ n_k \\in \\mathbb{Z} $ and $ x_k \\in \\mathbb{Z} $ be given, with:  \n- $ 2 \\leq n_k \\leq 10^5 $,  \n- $ 1 \\leq x_k \\leq 2n_k $,  \n- $ \\sum_{k=1}^t n_k \\leq 10^5 $.  \n\nLet $ P_k = (p_{k,1}, p_{k,2}, \\dots, p_{k,2n_k}) $ be a permutation of $ \\{1, 2, \\dots, 2n_k\\} $.\n\n**Constraints**  \n1. $ \\sum_{k=1}^t n_k \\leq 10^5 $  \n2. For each $ k $, $ P_k $ must satisfy:  \n   $$\n   \\sum_{i=1}^{n_k} |p_{k,2i-1} - p_{k,2i}| = x_k\n   $$\n\n**Objective**  \nFor each test case $ k $, output a permutation $ P_k $ satisfying the above constraint, or $-1$ if no such permutation exists.","simple_statement":null,"has_page_source":false}