“Make a new track” 是游戏 “Umamusume” 中的一种新模式。在游戏中，共有 $n$ 个回合来提升属性，每个回合可以选择休息（rest）、训练（train）或比赛（race）。
- 休息（rest）：增加 50 TP。
- 训练（train）：消耗 50 TP 并增加 15 点速度（TP 小于 50 时无法进行）。
- 比赛（race）：消耗 50 TP 并增加 100 G（TP 小于 50 时无法进行）。
第一回合开始时，你有 100 TP。
你可以在特殊商店中花费 G 来获取道具。特殊商店每 6 个回合刷新一次可购买的道具（第 6 回合是最早可以购买道具的时间）。每个道具出现在商店中的概率为 $p$（商店中可能存在什么都不卖的情况，且同一种道具的数量只有一件）。不同道具的价格和功能如下：
| 道具名称 | 价格 | 功能 |
|---|---|---|
| TP Medicine(L) | 100G | 增加 100 TP |
| TP Medicine(M) | 50G | 增加 50 TP |
| TP Medicine(S) | 25G | 增加 25 TP |
| Magic Book(L) | 100G | 增加 15 点速度 |
| Magic Book(M) | 50G | 增加 7 点速度 |
| Magic Book(S) | 25G | 增加 3 点速度 |
| Horn | 100G | 下次训练速度点数变为 2 倍 |
| Weight | 200G | 下次训练消耗 100 TP 但速度点数变为 3 倍 |
（Weight 不能与 Horn 同时使用）
每种道具可以购买多次，且你可以在购买后的任何回合使用道具。为了在游戏中获得最强、最快的 umamusume，你预先知道商店中所有的道具，并且你非常聪明。你想要计算期望的速度点数。
请输出结果对 $10^9 + 7$ 取模后的值。
输入格式
输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 10000$)，表示测试数据的组数。
每组测试数据包含两个整数 $n$ 和 $p$ ($0 \le n \le 10^9, 0 \le p < 10^9 + 7$)，分别表示回合数和每个道具出现在商店中的概率。
输出格式
对于每组测试数据，输出一个整数，表示期望的速度点数对 $10^9 + 7$ 取模后的结果。
样例
样例输入 1
3 2 1 5 500000004 27 500000004
样例输出 1
30 45 857330545