Subly found a set of Numbers in his Dad's table. Subly examines that set and wants to know how many numbers in that set are not divisible by his favourite number. 

He asked his brother for help. His brother told him that the numbers were in some row of the Pascals Triangle. But since he was busy, he couldn't solve Subly's problem.

Subly wants you to answer his question. You are given two integers N and M. 

The set of Numbers are in the Nth row of the Pascals Triangle and The Set contains Exactly N+1 numbers.

Second Integer denotes Subly's Number. It is guaranteed that M is a Prime number.

Input:

N And M are in a Single Line, Seperated by a single space.

Constraints:

1 ≤ N ≤ 10000000

1 ≤ M ≤ 1000

Examples:

Input:

7 5

Output:

6

Input:

8 2

Output:

2

Input:

5 3

Output:

6

SAMPLE INPUT
7 5

SAMPLE OUTPUT
6
from sys import stdin
n,m = map(int,stdin.readline().split())
tot = 0
cur = n
ans = 0
while cur:
	tot += cur/m
	cur/=m
for i in xrange(n+1):
	fir = n-i
	sec = i
	u = 0
	v = 0
	while fir:
		u += fir/m
		fir/=m
	while sec:
		v += sec/m
		sec/=m
	#print i,n-i,u,v
	if u+v >= tot:
		ans+=1
print ans