Description

rain_871 wants to make a cake for windy. Now she has a cake with size of 1*n grids. And she has m colors of butter. She wants to paint the cake with the m colors of butter. Moreover she wants to use every color at least once! And she wants to make the neighbor grid's color different. How many ways can she make this cake?

Input

Multiple test cases. Each contains two integers n and m. ( 1 <= n <= 10^9 ) ( 1 <= m <= 10^3 )

Output

For each test case,output only one line,the answer mod 19871118.

Sample Input

1 1 2 1 2 2 1 2 2 3 126948641 611

Sample Output

1 0 2 0 0 9972180

Author

windy7926778
Special for my good friend rain_871 once more!