"Makea newtrack" is a new mode of game "Umamusume".During the game,there will be �n rounds to improve attributes,each round can choose between rest,train or race.
����rest:add 50 TP
�����train:spend 50 TP and add 15 speed points(TP less than 50 will fail)
����race:spend 50 TP and add 100 G(TP less than 50 will fail)
At first round,you have 100 TP.
You can spend G in a special store to obtain items,special store will refresh the items that can be buy every 6 rounds(Round 6 will be the earliest time to buy items).The probability of each item appearing in the store is �p(It can exist in a store and not sell anything and the number of one type of item is only one).Different item have different price and features:
| item name | price | function |
|---|---|---|
| TP Medicine(L) | 100G | add 100 TP |
| TP Medicine(M) | 50G | add 50 TP |
| TP Medicine(S) | 25G | add 25 TP |
| Magic Book(L) | 100G | add 15 speed points |
| Magic Book(M) | 50G | add 7 speed points |
| Magic Book(S) | 25G | add 3 speed points |
| Horn | 100G | next training speed points will become 2x |
| Weight | 200G | next training speed points will spend 100 TP but become 3x |
| (Weight can not be used together with Horn) |
Each item can be bought more than one time and you can use the item on any round after you buy it.
In order to obtain the strongest and fastest umamusume in the game,you know all the items in the store at first,and you are smart.You want to know the expected speed points.
Please output it modulo 109+7109+7.
The input consists of multiple test cases. The first line contains a single integer �(1≤�≤10000)T(1≤T≤10000) — the number of test cases.
The each test case contains contains two integers �nand �p (0≤�≤109,0≤�<109+7)(0≤n≤109,0≤p<109+7)—This means that the number of rounds and the probability of each item appearing in the store.
3
2 1
5 500000004
27 50000000430
45
857330545