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?
Multiple test cases.
Each contains two integers n and m.
( 1 <= n <= 10^9 )
( 1 <= m <= 10^3 )
For each test case,output only one line,the answer mod 19871118.
Special for my good friend rain_871 once more!