You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

双重打击是《金铲铲之战》$s15$赛季的一种强化果实效果，它可以让英雄有一定几率在攻击时触发额外的攻击。假设触发的额外攻击也能触发双重打击的效果，你能计算出初始一次攻击造成 $x$ 次攻击（包括初始一次攻击和触发的额外攻击次数）的概率吗

题目以百分数的形式给出双重打击的触发概率，给出正整数 $y$ 代表概率为 $y\%$

因为答案过大，请输出对 $1e9+7$ 取模之后的答案
分数取模：$a$ $/$ $b$ $\% P$ $=$ $a$ $*$ $b^{-1}$ $\%$ $P$ , $b^{-1}$ 是 $b$ 在模 $P$ 意义下的逆元

Format

Input

第一行一个正整数 $T(1 \leq T \leq 1e5)$ 代表有 $T$ 组测试数据：

然后有 $T$ 行:

第 $i$ 行两个正整数 $x(1 \leq x \leq 1e9)$ 和 $y(0 \leq y \leq 100)$ 分别表示第 $i$ 组测试数据询问的造成攻击次数为 $x$ 和双重打击触发的概率为 $y\%$

Output

输出有 $T$ 行：

第 $i$ 行输出一个整数代表第 $i$ 组测试数据的答案

Samples

5
1 50
2 50
3 50
4 50
5 50

500000004
250000002
125000001
562500004
281250002