Saimon is a British Billionaire and he wanted to spend his last Christmas vacation in Northern Canada. So, he took a couple of his friends and sailed his yacht on a sunny day in December. But after four days, while passing through the North Atlantic Ocean his ship hit an iceberg and everyone but him died. Somehow, he managed to survive and reached a new island country. The island was so beautiful and full of magical events.
Since Saimon is a successful businessman, among all the magical events, a business model attracted him the most. While observing the model for a couple of weeks, he found some interesting facts about this model. A special type of currency named Emm coin is used for all the transactions in this small island country. By investing in a pair of Emm coins, from the fourth day and on, it is possible to make a profit of another pair of Emm coins. Saimon somehow managed $$$k$$$ pairs of Emm coins. Based on the information about the magical business model, how many Emm coins would he have after $$$n$$$ days?
He tried to find the answer, but failed. In fact, he is great in business but poor in Math. So, he contacted your team and asked you to solve this problem for him.
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains two integers $$$k$$$ and $$$n$$$ $$$\left(1 \leq k \leq 1000;\ 1 \leq n \leq 10^5\right)$$$ — the number of Emm coin pairs Saimon initially had and the total number of days.
For each test case, output the number of Emm coins Saimon would have after $$$N$$$ days. Your answer might be arbitrarily large, so output the answer modulo $$$10^9+7$$$.
31 41 81 10
Case 1: 4 Case 2: 18 Case 3: 38
