小红的概率

题号：NC317579
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小红拿到了两个长为 $n$ 的数组 $a,b$ ，现在她想生成一个新数组 $c$ ，具体规则如下：
$\hspace{23pt}\bullet$ 对于 $c$ 的第 $i$ 个元素 $c_i$ ，有 $\tfrac{1}{2}$ 的概率 $c_i = a_i$ ，剩余 $\tfrac{1}{2}$ 的概率 $c_i = b_i$ ，每一位的概率独立。
$\hspace{15pt}$ 小红想知道，最终得到的数组 $c$ 恰好是一个长为 $n$ 的排列的概率是多少？请将答案对 $1000000007$ 取模后输出。

【名词解释】
$\hspace{15pt}$ 长度为 $n$ 的排列：由 $1,2,\dots,n$ 这 $n$ 个整数、按任意顺序组成的数组（每个整数均恰好出现一次）。例如， $\{2,3,1,5,4\}$ 是一个长度为 $5$ 的排列，而 $\{1,2,2\}$ 和 $\{1,3,4\}$ 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。
$\hspace{15pt}$ 取模：可以证明答案可以表示为一个不可约分数 $\tfrac{p}{q}$ ，为了避免精度问题，请直接输出整数 $\left(p \times q^{-1} \bmod M\right)$ 作为答案，其中 $M = (10^9+7)$ ， $q^{-1}$ 是满足 $q\times q^{-1} \equiv 1 \pmod{M}$ 的整数。更具体地，你需要找到一个整数 $x \in [0, M)$ 满足 $x \times q$ 对 $M$ 取模等于 $p$ ，您可以查看样例解释得到更具体的说明。/
$\hspace{15pt}$ 本题中，如果您需要使用到除法的取模，即计算 $\left(p\times q^{-1} \bmod M\right)$ 时， $q^{-1}$ 需要使用公式 $\left(q^{M-2} \bmod M \right)$ 得到。例如，计算 $\tfrac{5}{4} \bmod M$ ：

$\begin{array}{rll} 4^{-1} & = & \left(4^{M-2} \bmod M\right) \\ & = & 250\,000\,002 \\ \hline \left(\tfrac{5}{4} \bmod M\right) & = & 5 \times4^{-1} \bmod M \\ & = & 5 \times 250\,000\,002 \bmod M \\ & = & 250\,000\,003 \end{array}$

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行输入一个整数 。
第二行输入  个整数 。
第三行输入  个整数 。

除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每组测试数据，新起一行。

输出一个整数，代表答案对  取模后的值。

示例1

输入

复制

输出

复制

250000002
0