Round Table Banquet

A long time ago, a king held a banquet to celebrate his birthday, and he invited lots of guests sitting in a large round table. The king prepared several kinds of food, and he wants any two guests sit at a distance of three enjoys different kind of food.
But how many plans can be there? Because the number can be huge, output the its last four digits will be fine.

There are multiple test cases, each test case contains two positive numbers n (4<=n<=10000000000) and m (2<=m<=100), indicates the number of guests and the kinds of food.
The input is terminated when n=m=0.

For each test case, output four digits, indicates the last four digits of the number of plans.

5 2
5 3
0 0

0000
0030

2009 Multi-University Training Contest 19 - Host by BNU