巨龙守卫

Problem Description

你拥有一支含 $n$ 个士兵的军队，军队中的每个士兵都有一个独立的力量值 $a_i$ 。 某天你接到命令，率部前去探索地牢；很不巧，你们在地牢的入口遇到了两只巨龙，巨龙不希望一支过强的力量进入地牢：

• 第一只龙会把军团中所有士兵的力量值累加（得到 $S_1=\sum_{i=1}^n a_i$ ），并将其与一个固定的值 $V_1$ 比较；若 $S_1 > V_1$ ，第一只龙将绝不允许你们进入地牢；
• 第二只龙跟第一只龙的想法差不多，但它的脑子不太灵光，忘了做加法要进位：它把军团中所有士兵的力量值作异或和（得到 $S_2=\oplus_{i=1}^n a_i$ ），并将其与一个固定的值 $V_2$ 比较；若 $S_2 > V_2$ ，第二只龙将绝不允许你们进入地牢；
• 当且仅当 $S_1 \leq V_1$ 且 $S_2 \leq V_2$ 时，你们才能在两只巨龙的许可下进入地牢。 由于统一的军事化训练，每个士兵的力量值 $a_i$ 都在一个固定的范围 $[l,r]$ 之间（必须是整数）。假设你可以在范围内任意选择每个士兵的力量值，请问有多少种选择方案可以使军队进入地牢？ （由于答案可能很大，请将答案对 $10^9+7$ 取模后再输出。）

Input

第一行含一个正整数 $t ~ (1 \le t \le 200)$ ，表示数据组数；接下来对于每组数据： 每组数据仅占一行，依次给出 $5$ 个整数 $ n ~ (1 \leq n \leq 10),l,r ~ (1 \leq l \leq r \leq 10^9),V_1,V_2 ~ (1 \leq V_1,V_2 \leq 10^9) $ ，含义见上。 保证 $\sum n \leq 1500$ 。

Output

对于每组数据，输出一个非负整数独占一行，表示“可以使军队进入地牢的力量值选择方案数”对 $10^9+7$ 取模后的结果。

Sample Input

6
3 2 4 12 5
3 2 4 7 5
3 2 4 11 5
3 2 4 5 7
5 2 17 29 22
10 1 144569238 930683052 246860315

Sample Output

27
4
26
0
41924
992128947

Hint

两种力量值选择方案被视作不同，当且仅当任一士兵的力量值在两方案中不同。

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（3）