题目描述

Alice 和 Bob 在博弈，每一轮中 Alice 有 $p$ 的概率胜利，$1-p$ 的概率失败，双方初始得分均为 $0$。某个人胜利时，他会获得 $1$ 分，否则扣 $1$ 分。

由于计数器无法正常表示负数，所以如果某个人失败时是 $0$ 分，那么他就不会被扣分。当然，此时对方的加分不受影响。

游戏一共要进行 $n+m$ 轮，Alice 想请你帮她算算游戏结束时她的期望得分。

“这算啥，我小 L 分分钟搞定！”。比小 L 更熟练的你当然也是随手就算出来了，但就在你打算告诉 Alice 答案之前，博弈论世界之神——temporaryDO 出现了，他给大家带来了一个重要信息：这 $n+m$ 轮游戏中，Alice 恰好赢了 $n$ 轮！

熟知条件概率的你意识到，你需要修改自己的计算方法来得到正确的答案了。

为了避免精度问题，请将结果对 $10^9+7$ 取模。可以证明答案是一个有理数 $\frac{p}{q}$，且 $10^9+7\nmid q$，你只需要找到一个整数 $x\in [0, 10^9+7)$ 使得 $qx\equiv p\pmod{10^9+7}$，可以证明这样的 $x$ 唯一。

输入格式

从文件 prob.in 中读入数据。

本题有多组测试数据。

输入的第一行包含两个正整数 $T,P'$，其中 $T$ 表示测试数据组数，$\frac{P'}{1000}$ 表示 $p$，即 Alice 在每轮游戏中的获胜概率。

接下来 $T$ 行，每行两个非负整数 $n,m$，表示一组测试数据。

输出格式

输出到文件 prob.out 中。

输出 $T$ 行，每行一个整数，表示对应测试数据的答案。

样例 1 输入

3 500
1 1
2 3
4 4

样例 1 输出

500000004
200000002
728571435

样例 1 解释

每一轮游戏 Alice 均有 $\frac{1}{2}$ 的概率胜利。

• 对于第一组数据，Alice 的胜利可能在第一轮或第二轮，并且概率相等。若她在第一轮胜利，则最终得分为 $0$，否则她的得分为 $1$。故期望为 $\frac{1}{2}$，验证发现 $2\times 500000004\equiv 1\pmod{10^9+7}$。
• 对于第二组数据，所求期望为 $\frac{3}{5}$。
• 对于第三组数据，所求期望为 $\frac{93}{70}$。

样例 2

见选手目录下的 prob2.in 与 prob2.ans。

该样例满足测试点 $2,3$ 的限制。

样例 3

见选手目录下的 prob3.in 与 prob3.ans。

该样例满足测试点 $4,5$ 的限制。

样例 4

见选手目录下的 prob4.in 与 prob4.ans。

该样例满足测试点 $8\sim10$ 的限制。

数据范围

对于所有测试数据，保证：$0\le n+m,T\le2.5\times10^5,0<P'<1000$。

特殊性质 A：$|n-m|\le200$。