Round Table Banquet

Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 3098
64-bit integer IO format: %I64d      Java class name: Main

Description

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.

Input

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.

Output

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

Sample Input

5 2
5 3
0 0

Sample Output

0000
0030

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .