{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003cp\u003eSanvi is very busy girl. So you have been given enough time (1000 milliseconds) to help him.\u003c/p\u003e\r\n\u003cp\u003eSanvi has a bag of marbles with different letters written on them. And she has become busy on playing with these marbles by putting them in N boxes placed in a row. There are exactly M distinct type of marbles, N of each type.\u003c/p\u003e\r\n\u003cp\u003eNow she puts only N marbles (out of M*N) in N boxes, one by one and upon completion she writes down the letters on the marbles on a paper to form a string. As Sanvi hates palindrome strings (strings which read same from both sides e.g. MADAM), she erases palindrome string from the paper as soon as she finds one.\u003c/p\u003e\r\n\u003cp\u003eNow she is wondering how many different strings she might get on her paper if she could try all possible combination of putting the marbles in the boxes. So you have to help her by answering. As there could be many strings so print it modulo 1,000,000,007.\u003c/p\u003e\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eInput starts with an integer TC (\u0026lt;\u003d10), denoting the number of test cases. Each case starts with two non negative integers N (\u0026lt;\u003d100000) and M (\u0026lt;\u003d26) as described above.\u003c/p\u003e\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eFor each case, print the case number and total number of strings written on the paper modulo 1000000007.\u003c/p\u003e\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\u003cdiv\u003e\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\u003e2\n2 2\n2 3\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 2 \nCase 2: 6\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/div\u003e\n\u003c/div\u003e"}}]}