+ Time Limit: 3 seconds + Memory Limit: 256 megabytes --- Mohammadsam has recently become interested in participating in various lotteries. In the latest lottery he participated in, he was given an \(n\)-digit code consisting of the digits \(1\), \(2\), and \(3\). He defines a luckiness index for himself so that he can use it to guess whether he might win the lottery or not. For an \(x\)-digit code called \(s\), whose digits are \(s_1\) through \(s_x\), he defines the attractiveness of that code as the number of indices \(i\) such that $$ 1 \leq i \leq x-1 $$ and $$ s_i < s_{i+1} $$ and denotes it by \(G(s)\). (The attractiveness of a 0-digit code is defined as \(0\).) In other words, \(G(s)\) represents the number of positions in code \(s\) where the digit is smaller than the next digit. He defines the luckiness of an \(n\)-digit lottery code \(s\) as the sum of \(G(a)^k\) over all \(2^n\) subsequences of code \(s\), where \(k\) is a fixed number given as input for each test case, and \(a\) is a subsequence of \(s\). More precisely, the luckiness of a code is defined by the following expression: $$ \sum_{m=0}^{n} \; \sum_{1\le i_1<i_2<\cdots<i_m\le n} G(s_{i_1}s_{i_2}\cdots s_{i_m})^k $$ Mohammadsam has not received his lottery code yet and does not know how lucky it will be. However, he knows that this code will be an \(n\)-digit code with digits \(1\), \(2\), and \(3\). He knows that his lottery code will be chosen randomly and with equal probability from the \(3^n\) possible \(n\)-digit codes (with digits \(1\), \(2\), and \(3\)). Now he asks you to calculate the expected value of the luckiness of the lottery code Mohammadsam will receive, modulo \(10^9+7\), based on this information. It can be shown that the answer can be represented as an irreducible fraction $$ \frac{p}{q} $$ where \(p\) and \(q\) are integers and \(q \neq 0\), and you should output $$ p \cdot q^{-1} \pmod{10^9+7} $$ where \(q^{-1}\) is the multiplicative inverse of \(q\) modulo \(10^9+7\). \**Notes:** A subsequence of a code \(s\) is a sequence obtained by deleting some elements of \(s\), which may include all elements or none of them. A code of length \(n\) has \(2^n\) subsequences. # Input The input consists of \(T\) different test cases, and each test case should be solved independently. The first line contains an integer \(T\), followed by \(T\) lines. Each of the next \(T\) lines contains two integers \(n\) and \(k\), representing the length of the lottery code and the fixed number \(k\), respectively. $$ 1 \leq T \leq 50 $$ $$ 1 \leq n \leq 10^{18} $$ $$ 1 \leq k \leq 50 $$ It is guaranteed that the sum of the values of \(k\) over all test cases does not exceed \(50\). # Output In one line, calculate the expected value of the luckiness of Mohammadsam's lottery code (while this code is chosen randomly and with equal probability). # Example ## Sample Input 1 ``` 3 1 1 5 2 10 10 ``` ## Sample Output 1 ``` 0 148148169 525754884 ```