{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003clink href\u003d\"css/light_oj.css\" rel\u003d\"stylesheet\" type\u003d\"text/css\" /\u003e\r\n\u003cp class\u003d\"MsoNormal\"\u003e\r\n\tYou are a necklace maker. You like this task because it\u0026#39;s challenging, fascinating and of course makes a lot of money. Now, you want to make a necklace consisting of \u003cb\u003en\u003c/b\u003e beads. The beads are connected in the following fashion:\u003c/p\u003e\r\n\u003cp class\u003d\"MsoListParagraphCxSpFirst\" style\u003d\"text-align:justify;text-indent:-.25in\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;line-height:115%;font-family:\u0026quot;Garamond\u0026quot;,\u0026quot;serif\u0026quot;\"\u003e1)\u003cspan style\u003d\"font:7.0pt \u0026quot;Times New Roman\u0026quot;\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; \u003c/span\u003e\u003c/span\u003e\u003cspan style\u003d\"font-size:12.0pt;line-height:115%;font-family:\u0026quot;Garamond\u0026quot;,\u0026quot;serif\u0026quot;\"\u003eBead \u003cb\u003ei (1 \u0026lt; i \u0026lt; n)\u003c/b\u003e is connected with bead \u003cb\u003ei - 1\u003c/b\u003e and bead \u003cb\u003ei + 1\u003c/b\u003e.\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoListParagraphCxSpMiddle\" style\u003d\"text-align:justify;text-indent:-.25in\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;line-height:115%;font-family:\u0026quot;Garamond\u0026quot;,\u0026quot;serif\u0026quot;\"\u003e2)\u003cspan style\u003d\"font:7.0pt \u0026quot;Times New Roman\u0026quot;\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; \u003c/span\u003e\u003c/span\u003e\u003cspan style\u003d\"font-size:12.0pt;line-height:115%;font-family:\u0026quot;Garamond\u0026quot;,\u0026quot;serif\u0026quot;\"\u003eThe first bead is connected with the second bead and the \u003cb\u003en\u003csup\u003eth\u003c/sup\u003e\u003c/b\u003e bead.\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoListParagraphCxSpLast\" style\u003d\"text-align:justify;text-indent:-.25in\"\u003e\r\n\t\u003cspan style\u003d\"font-size:12.0pt;line-height:115%;font-family:\u0026quot;Garamond\u0026quot;,\u0026quot;serif\u0026quot;\"\u003e3)\u003cspan style\u003d\"font:7.0pt \u0026quot;Times New Roman\u0026quot;\"\u003e\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp;\u0026nbsp; \u003c/span\u003e\u003c/span\u003e\u003cspan style\u003d\"font-size:12.0pt;line-height:115%;font-family:\u0026quot;Garamond\u0026quot;,\u0026quot;serif\u0026quot;\"\u003eThe \u003cb\u003en\u003csup\u003eth\u003c/sup\u003e\u003c/b\u003e bead is connected with the first bead and the \u003cb\u003e(n-1)\u003csup\u003e\u003cspan data-scayt_word\u003d\"th\" data-scaytid\u003d\"1\"\u003eth\u003c/span\u003e\u003c/sup\u003e\u003c/b\u003e bead.\u003c/span\u003e\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNormal\"\u003e\r\n\t\u003cspan style\u003d\"line-height:115%\"\u003eNow you have \u003cb\u003eK\u003c/b\u003e colors and each bead can be colored using one of the \u003cb\u003eK\u003c/b\u003e colors. You have to find the number of possible necklaces you can make using these colors. Two necklaces will be considered same if one can be rotated to another.\u003c/span\u003e\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp class\u003d\"MsoNormal\"\u003e\r\n\tInput starts with an integer \u003cb\u003eT (\u003c/b\u003e\u003cb\u003e\u0026le; 300)\u003c/b\u003e, denoting the number of test cases.\u003c/p\u003e\r\n\u003cp class\u003d\"MsoNormal\"\u003e\r\n\tEach case starts with a line containing two integers: \u003cb\u003en\u003c/b\u003e and \u003cb\u003eK (1 \u0026le; n \u0026le; 1000, 1 \u0026le; K \u0026le; 10\u003csup\u003e9\u003c/sup\u003e)\u003c/b\u003e.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp class\u003d\"MsoNormal\"\u003e\r\n\tFor each case, print the case number and the total number of possible necklaces modulo\u003cb\u003e 1000000007\u003c/b\u003e.\u003c/p\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cp class\u003d\"MsoNormal\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt\"\u003e\r\n\t\u0026nbsp;\u003c/p\u003e\r\n\u003cp\u003e\r\n\t7\u003c/p\u003e\r\n\u003cp\u003e\r\n\t4 2\u003c/p\u003e\r\n\u003cp\u003e\r\n\t5 7\u003c/p\u003e\r\n\u003cp\u003e\r\n\t5 2\u003c/p\u003e\r\n\u003cp\u003e\r\n\t4 8\u003c/p\u003e\r\n\u003cp\u003e\r\n\t4 3\u003c/p\u003e\r\n\u003cp\u003e\r\n\t5 3\u003c/p\u003e\r\n\u003cp\u003e\r\n\t5 5\u003c/p\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cp class\u003d\"MsoNormal\" style\u003d\"margin-bottom:0in;margin-bottom:.0001pt\"\u003e\r\n\t\u0026nbsp;\u003c/p\u003e\r\n\u003cp\u003e\r\n\tCase 1: 6\u003c/p\u003e\r\n\u003cp\u003e\r\n\tCase 2: 3367\u003c/p\u003e\r\n\u003cp\u003e\r\n\tCase 3: 8\u003c/p\u003e\r\n\u003cp\u003e\r\n\tCase 4: 1044\u003c/p\u003e\r\n\u003cp\u003e\r\n\tCase 5: 24\u003c/p\u003e\r\n\u003cp\u003e\r\n\tCase 6: 51\u003c/p\u003e\r\n\u003cp\u003e\r\n\tCase 7: 629\u003c/p\u003e"}}]}