你拥有一支含 $n$ 个士兵的军队，军队中的每个士兵都有一个独立的力量值 $a_i$。

某天你接到命令，率部前去探索地牢；很不巧，你们在地牢的入口遇到了两只巨龙，巨龙不希望一支过强的力量进入地牢：

• 第一只龙会把军团中所有士兵的力量值累加（得到 $S_1=\sum_{i=1}^n a_i$），并将其与一个固定的值 $V_1$ 比较；若 $S_1>V_1$，第一只龙将绝不允许你们进入地牢；
• 第二只龙跟第一只龙的想法差不多，但它的脑子不太灵光，忘了做加法要进位：它把军团中所有士兵的力量值作异或和（得到 $S_2=\bigoplus_{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$ 取模后再输出。）

输入格式

第一行含一个正整数 $t$（$1\leq t\leq 200$），表示数据组数；接下来对于每组数据：

每组数据仅占一行，依次给出 $5$ 个整数 $n,l,r,V_1,V_2$（$1\leq n\leq 10,1\leq l\leq r\leq 10^9,1\leq V_1,V_2\leq 10^9$），含义见上。

保证 $\sum n\leq 1500$。

输出格式

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

样例

输入

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

输出

27
4
26
0
41924
992128947

样例解释

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