Description

"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:

(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 + 7.

Input

The input consists of multiple test cases. The first line contains a single integer T (1 ≤ T ≤ 10000) — the number of test cases. The each test case contains contains two integers nand p (0 ≤ n ≤ 109, 0 ≤ p < 109 + 7)—This means that the number of rounds and the probability of each item appearing in the store.

ouput

For each test case, output an integer representing the expected speed points modulo 109 + 7.

Example

Input：

3
2 1
5 500000004
27 500000004

ouput：

30
45
857330545