Ash goes to a shop which has n different items. The price of each of the items is 1 unit . Ash is a rich guy and has infinite coins each of value k units. Now he wants to buy some of the items, but he wants to make sure that he can pay for all the items he buys using the coins he has. Formally, the total price of the items he buys must be a multiple of k.
Find the number of ways in which he can buy some of the items from the shop. Since this number can be pretty huge, print only last 5 digits of the answer.
Two ways are considered distinct if there exists an i, such that item i is bought in only one of them. Buying no item is also a valid way.

Input:
The only line in the input contains two integers separated by a space, n and k.

Output:
Print the last 5 digits of the number of ways in which he can buy some of the items, as specified above.

Constraints:
$1 \leq n \leq 10^{13}$
$1 \leq k \leq 10^4$