
ZOJ Problem Set  4084
Little Sub has a friend called Heltion. When he knows that Mr.Potato has given a hard Math problem to Little Sub, he decides to help Little Sub fight back. Therefore, along with Little Sub, Heltion locks Mr.Potato's fridge with an electronic lock, which requires a password to open. Then Heltion leaves a message to Mr.Potato: "The password is the answer to this easy Math problem. Please solve it." Well, Mr.Potato cannot solve this Math problem. Please help him. There are $n$ fans $F_1, F_2, \dots, F_n$ and $m$ teams $T_1, T_2, \dots, T_m$.
Please tell Mr.Potato that the number of ways relating the fans to the teams satisfying the restrictions above. Two ways are considered different if there exists a team such that this team has different sets of fans in these two ways. InputThere are multiple test cases. The first line of the input contains an integer $T$($1 \le T \le 10^5$), indicating the number of test cases. For each test case: The first and only line contains two integers $n$ and $m$ ($1\leq n\leq10^{18}$, $2\leq m\leq 6$). OutputFor each test case, output an integer representing the answer modulo 1000000007 ($10^9+7$) in one line. Sample Input9 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 Sample Output2 12 36 216 1032 7200 46800 453600 3369600 NoteFor the first sample case, there are $2$ ways relating the fans to the teams:
Author: LYU, Yaowei Source: ZOJ Monthly, January 2019 