{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\r\nLittle 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\u0027s 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.\"\r\n\u003c/p\u003e\n\n\u003cdiv style\u003d\"text-align: center;\"\u003e\n\t\u003cimg height\u003d\"384\" src\u003d\"CDN_BASE_URL/9d0966a812868bd0133ffd2841c0126b?v\u003d1714937116\" alt\u003d\"“math”/\"\u003e\n\u003c/div\u003e\n\n\u003cp\u003e\nWell, Mr.Potato cannot solve this Math problem. Please help him.\n\u003c/p\u003e\r\n\u003cp\u003e\r\nThere are $n$ fans $F_1, F_2, \\dots, F_n$ and $m$ teams $T_1, T_2, \\dots, T_m$.\r\n\u003c/p\u003e\u003col\u003e\r\n \u003cli\u003eFor any fan $F_i$, $F_i$ is a fan of at least one team but not a fan of all teams;\u003c/li\u003e\r\n \u003cli\u003eFor any two teams $T_{i}, T_{j}$($1 \\leq i,j \\leq m$), there exists exactly one team $T_{k}$($1 \\leq k \\leq m$) \u003cb\u003eexactly\u003c/b\u003e having the fans \u003cb\u003eboth\u003c/b\u003e $T_{i}$ and $T_{j}$ have. Note that $i,j,k$ can be the same;\u003c/li\u003e\r\n \u003cli\u003eFor any two teams $T_{i}, T_{j}$($1 \\leq i,j \\leq m$), there exists exactly one team $T_{k}$($1 \\leq k \\leq m$) \u003cb\u003eexactly\u003c/b\u003e having the fans \u003cb\u003eeither\u003c/b\u003e $T_{i}$ or $T_{j}$ have. Note that $i,j,k$ can be the same.\u003c/li\u003e\r\n\u003c/ol\u003e\n\r\n\u003cp\u003e\r\nPlease 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.\r\n\u003c/p\u003e\r\n\r\n\u003ch4\u003eInput\u003c/h4\u003e\r\n\u003cp\u003e\r\nThere 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:\n\u003c/p\u003e\n\u003cp\u003e\r\nThe first and only line contains two integers $n$ and $m$ ($1\\leq n\\leq10^{18}$, $2\\leq m\\leq 6$).\r\n\u003c/p\u003e\r\n\r\n\u003ch4\u003eOutput\u003c/h4\u003e\r\n\u003cp\u003e\r\nFor each test case, output an integer representing the answer modulo 1000000007 ($10^9+7$) in one line.\r\n\u003c/p\u003e\r\n\r\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e9\r\n2 2\r\n2 3\r\n3 3\r\n3 4\r\n4 4\r\n4 5\r\n5 5\r\n5 6\r\n6 6\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n12\r\n36\r\n216\r\n1032\r\n7200\r\n46800\r\n453600\r\n3369600\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n\u003ch4\u003eNote\u003c/h4\u003e\r\n\u003cp\u003e\r\nFor the first sample case, there are $2$ ways relating the fans to the teams:\r\n\u003c/p\u003e\u003col\u003e\r\n \u003cli\u003e$F_1$ is a fan of $T_1$ and $F_2$ is a fan of $T_1$;\u003c/li\u003e\r\n \u003cli\u003e$F_1$ is a fan of $T_2$ and $F_2$ is a fan of $T_2$.\u003c/li\u003e\r\n\u003c/ol\u003e\r\n\u003cp\u003e\u003c/p\u003e"}}]}