{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"![项链][1]\n你是一名项链制作师。你喜欢这个任务,因为它具有挑战性、迷人,当然还能赚很多钱。现在,你想要制作一个由 **n** 颗珠子组成的项链。这些珠子连接方式如下:\n\n1. 第 **i (1 \u0026lt; i \u0026lt; n)** 颗珠子与第 **i - 1** 颗和第 **i + 1** 颗相连。\n2. 第一颗珠子与第二颗和第 **n\u003csup\u003eth\u003c/sup\u003e** 颗相连。\n3. 第 **n\u003csup\u003eth\u003c/sup\u003e** 颗珠子与第一颗和第 **(n-1)\u003csup\u003eth\u003c/sup\u003e** 颗相连。\n\n现在你有 **K** 种颜色,每颗珠子可以用这 **K** 种颜色之一着色。你需要找出使用这些颜色可以制作的项链数量。如果一个项链可以通过旋转变成另一个项链,则认为它们是相同的。\n\n例如,假设项链上有4颗珠子,你有两种颜色黄色和绿色,那么有6种可能的项链。它们是:\n\n\n\n| ![][2] | ![][3] | ![][4] | ![][5] | ![][6] | ![][7] |\n| ------ | ------ | ------ | ------ | ------ | ------ |\n\n\n\n[1]: https://static.lightoj.com/images/problem-1419/necklace1-1602925531708.png?rightme\n[2]: https://static.lightoj.com/images/problem-1419/necklace2-1602925827643.png\n[3]: https://static.lightoj.com/images/problem-1419/necklace3-1602925926983.png\n[4]: https://static.lightoj.com/images/problem-1419/necklace4-1602925981308.png\n[5]: https://static.lightoj.com/images/problem-1419/necklace5-1602926028944.png\n[6]: https://static.lightoj.com/images/problem-1419/necklace6-1602926068704.png\n[7]: https://static.lightoj.com/images/problem-1419/necklace7-1602926104139.png"}},{"title":"输入","value":{"format":"MD","content":"输入以一个整数 **T (\u0026le; 50)** 开始,表示测试用例的数量。\n\n每个测试用例以包含两个整数的一行开始:**n** 和 **K (1 \u0026le; n \u0026le; 1000, 1 \u0026le; K \u0026le; 10\u003csup\u003e9\u003c/sup\u003e)**。"}},{"title":"输出","value":{"format":"MD","content":"对于每个测试用例,输出案例编号和总可能项链数量,取模 **1000000007 (10\u003csup\u003e9\u003c/sup\u003e + 7)**。"}},{"title":"示例","value":{"format":"MD","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\u003e7\n4 2\n5 7\n5 2\n4 8\n4 3\n5 3\n5 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 6\nCase 2: 3367\nCase 3: 8\nCase 4: 1044\nCase 5: 24\nCase 6: 51\nCase 7: 629\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}