{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eBack in the day when Bhai and SRK used to have a rift between them we heard a lot of stories. One of the stories goes as: Once Bhai had to gift something to SRK on the success of his film. Confused bhai wasn\u0027t able to decide what gift he should give. Finally, he came up with an idea. \n\u003c/p\u003e\n\u003cp\u003eHe decided to gift an array of n integers such that each integer in the array is in the range \u003cb\u003e0 to 2\u003csup\u003ek\u003c/sup\u003e - 1\u003c/b\u003e both inclusive. Also to make the gift seem big the sum of all the integers in the array is as large as possible.\u003c/p\u003e\n\u003cp\u003e\nBut there was a twist:\nThe \u003ca href\u003d\"https://en.wikipedia.org/wiki/Bitwise_operation#AND\"\u003ebitwise AND\u003c/a\u003e of all its elements is \u003cb\u003e0\u003c/b\u003e; making the gift useless thus taunting SRK. \u003c/p\u003e\n\u003cp\u003e\nNow given two integers \u003cb\u003en\u003c/b\u003e and \u003cb\u003ek\u003c/b\u003e, Bhai wants to count the number of such arrays of length \u003cb\u003en\u003c/b\u003e such that all its elements are integers between \u003cb\u003e0\u003c/b\u003e and \u003cb\u003e2\u003csup\u003ek\u003c/sup\u003e-1\u003c/b\u003e (inclusive); the sum of its elements is as large as possible, but bitwise AND of all the elements is \u003cb\u003e0\u003c/b\u003e\u003c/p\u003e\n\n\u003cp\u003eSince the answer can be very large, print its remainder when divided by \u003cb\u003e10\u003csup\u003e9\u003c/sup\u003e+7\u003c/b\u003e.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains an integer \u003cb\u003et\u003c/b\u003e (\u003cb\u003e1 ≤ t ≤ 10\u003c/b\u003e) — the number of test cases you need to solve.\u003c/p\u003e\n\u003cp\u003eEach test case consists of a line containing two integers \u003cb\u003en\u003c/b\u003e and \u003cb\u003ek\u003c/b\u003e (\u003cb\u003e1 ≤ n ≤ 10\u003csup\u003e5\u003c/sup\u003e\u003c/b\u003e, \u003cb\u003e1 ≤ k ≤ 20\u003c/b\u003e) separated by space.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case, print the number of arrays satisfying the conditions. Since the answer can be very large, print its remainder when divided by \u003cb\u003e10\u003csup\u003e9\u003c/sup\u003e+7\u003c/b\u003e.\u003c/p\u003e"}},{"title":"Example","value":{"format":"HTML","content":"\u003cdiv class\u003d\"sample-test\"\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e2\n2 2\n100000 20\n\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e4\n226732710\n\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first example, the $$$4$$$ arrays are:\u003c/p\u003e\n\u003cul\u003e \n \u003cli\u003e \u003cb\u003e[3,0]\u003c/b\u003e, \u003c/li\u003e\n \u003cli\u003e \u003cb\u003e[0,3]\u003c/b\u003e, \u003c/li\u003e\n \u003cli\u003e \u003cb\u003e[1,2]\u003c/b\u003e, \u003c/li\u003e\n \u003cli\u003e \u003cb\u003e[2,1].\u003c/b\u003e \u003c/li\u003e\n\u003c/ul\u003e"}}]}