提示: 欢迎访问OurACM平台。
Problem 2289 项链

Accept: 26    Submit: 153
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

520要到了,Xenon打算送给Cherry一条项链,这条项链有m个镶孔,编号分别为0到m-1。Xenon手上有n种颜色不同的钻石,他想将钻石镶嵌在项链上,而且每个相邻的镶孔,镶嵌上的钻石颜色要不一样。

Xenon想知道他可以镶嵌出多少种不同的项链。

PS:第k号镶孔和第(k-1+m)%m以及(k+1+m)%m号镶孔这两个镶孔是相邻关系。假设m=9,那么0号和1号、8号相邻,3号和2号、4号相邻。

两条项链不同当且仅当存在编号k,两条项链的k号镶孔的钻石颜色不一样。

Input

题目包含多组测试数据,每组测试数据包含两个正整数n和m,分别表示钻石的颜色种数和一条项链所需要的钻石个数,以空格隔开。

n≤50,m≤10^18

Output

输出一个整数,表示Xenon可以制作出多少种项链。

由于答案很大,请将答案对1000000007(10^9+7)取余。

Sample Input

5 2

Sample Output

20

Source

福州大学第十五届程序设计竞赛_重现赛

Submit  Back  Status  Discuss