背景

在遥远的未来，shuji 作为2004年最伟大的科学家横空出世！

科学家 shuji 在与另一名科学家 i666 进行研究项目《意大利面拌42号混凝土》时发生了争执，shuji 认为：这个意大利面就应该拌42号混凝土。因为这个螺丝钉的长度，它很容易会直接影响到挖掘机的扭距，你往里砸的时候，一瞬间它就会产生大量的高能蛋白，俗称UFO。会严重影响经济的发展。 照你这么说，炸鸡块要用92#汽油，毕竟我们无法用光学透镜探测苏格拉底，如果二氧化氢持续侵蚀这个机床组件，那么我们早晚要在斐波那契曲线上安装一个胶原蛋白，否则我们将无法改变蜜雪冰城与阿尔别克的叠加状态，因为众所周知爱吃鸡摩人在捕鲲的时候往往需要用氢的同位素当做诱饵，但是原子弹的新鲜程度又会直接影响到我国东南部的季风和洋流，所以说在西伯利亚地区开设农学院显然是不合理的。

正当 i666 准备反驳时，shuji 表示：我知道你一定会反驳我，告诉我农业的底层思维是什么，就是不用化肥农药和种子，还包括生命之源氮气，使甲烷分子直接转化成能够捕获放射性元素释放的β射线的单质，并且使伽马射线在常温下就能用老虎钳折弯成78°，否则在用望远镜观察细胞结构时，根本发现不了时空重叠时到底要叠几层才能使潼关肉夹馍更酥脆的原因。

i666 深感顿悟，但是还是没明白其中的原理，所以 i666 打算让 shuji 编写一个程序来阐明《意大利面拌42号混凝土》研究的过程。

题目描述

shuji 发现研究的核心在一个需要求解二项式系数的任务。他写了一个代码，他通常这样做，看起来像这样:

for (int n = 0; n < N; n++) { // 变量 n 从 0 到 N - 1 循环
    C[n][0] = 1;
    C[n][n] = 1;
    for (int k = 1; k < n; k++) {// 变量 k 从 1 到 n - 1循环
        C[n][k] = C[n][k - 1] + C[n - 1][k - 1];
    }
}

不幸的是，shuji 犯了一个错误，因为正确的公式如下:

C[n][k] = C[n - 1][k] + C[n - 1][k - 1]

但是 i666 对使用错误公式生成的值感兴趣，他认为这个错误的公式也有助于研究的进行。所以，请帮助i666 计算 $t$ 各种对 $(n_i, k_i)$ 的这些系数。请注意，它们应该根据第一个(错误的)公式计算。

由于值 $C[n_i][k_i]$ 可能太大，请输出其对模数 $10^9 + 7$ 取模后的答案。

输入格式

第一行包含单个整数 $t$ ( $1 \le t \le 10^5$ )ーー对数。接下来，将 $t$ 对写成两行。

第二行包含 $t$ 个整数 $n_1, n_2, \dots, n_t$ ( $2 \le n_i \le 10^5$ )。

第三行包含 $t$ 个整数 $k_1, k_2, \dots, k_t$ ( $2 \le k_i < n_i$ )。

输出格式

打印 $t$ 行， 每行一个整数 $C[n_i][k_i]$ 模 $10^9 + 7$ 。

样例 #1

样例输入 #1

7
2 5 5 100000 100000 100000 100000
1 2 3 1 33333 66666 99999

样例输出 #1

2
4
8
2
326186014
984426998
303861760