Let  be a prime number and  be a positive integer. There are a total of  bars of chocolate at the shop, the -th of which sells at the price of  coins (). A total of  students are choosing presents for the coming Teachers' Day together. They decide to buy exactly  different bars of chocolate, and they hope that the number of coins they need to pay is divisible by , so that they can divide the bill equally. Please count the number of ways for the students to choose some chocolates, such that the total price is divisible by . Two ways of selecting are considered different, if there exists a bar chosen in one way but not in the other. As the answer may be too large, you just need to print it modulo .

给定质数  和正整数 。商店里有价格为  的巧克力各一盒。小朋友们想要从中选出  盒，使得价格的总和是  的倍数。请计算满足上述要求的选法数量。两种选法视作不同当且仅当存在一盒巧克力在一种选法被选而另一种选法中没有。由于答案可能很大，你只需要输出它对  取模后的值即可。