{"trustable":true,"prependHtml":"\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 async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003ecjj has k kinds of characters the number of which are infinite. He wants to build two strings with the characters. The lengths of the strings are both equal to n. \u003cbr\u003e\u003cbr\u003ecjj also define a cjj_val for two string.\u003cbr\u003ea[i,j] means the substring a[i],a[i+1],...,a[j-1],a[j] of string a.\u003cbr\u003e\u003cbr\u003ecjj_val \u003d max({ j-i+1 }) where a[i,j]\u003db[i,j] for every 0\u0026lt;\u003di\u0026lt;\u003dj\u0026lt;n.\u003cbr\u003e\u003cbr\u003eKnow cjj wants to know that if he wants to build two strings with k different characters whose cjj_val is equal to m, how many ways can he do that.\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of the input data is an integer T(1\u0026lt;\u003dT\u0026lt;\u003d100), means the number of test case.\u003cbr\u003e\u003cbr\u003eNext T lines, each line contains three integers n(1\u0026lt;\u003dn\u0026lt;\u003d1000000000), m(1\u0026lt;\u003dm\u0026lt;\u003d10), k(1\u0026lt;\u003dk\u0026lt;\u003d26).\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each test case, print one line, the number of the ways to build the string. The answer will be very large, you just need to output ans mod 1000000007."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\u003e2\r\n3 2 3\r\n3 3 3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e108\r\n27\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}