Nhân dịp có nhiều cao thủ tham gia contest Hướng tới những vì sao lần đầu của năm 2024, BTC xin dành tặng bài cuối cùng này như một thử thách thú vị: Cho số nguyên dương ~n~ và số nguyên tố ~p < n~. Một số nguyên ~m~ với ~1 \le m \le n~ được gọi là tốt nếu như ~C_n^m~ chia hết cho ~p~. Đếm số lượng số tốt.

Ở đây, hệ số nhị thức ~C_n^m~ xác định bởi công thức ~\frac{n!}{m!(n-m)!}.~

Input

Một dòng duy nhất gồm số nguyên dương ~n~ và số nguyên tố ~p~, trong đó ~1 \le n \le 10^{18}~ và ~2 \le p \le \min \{100,n \}.~

Output

Một dòng duy nhất cho biết số lượng số tốt.

Sample input 1

16 2

Sample output 1

15

Sample input 2

20 19

Sample output 2

17

Subtasks

Trong Ví dụ 1, ta thấy các số tốt sẽ bao gồm ~1,2,...,15~. Trong Ví dụ 2, ta đếm được các số tốt là ~2,3,...,18.~

• Có ~25\%~ số test của đề ứng với ~n \le 100.~

• Có ~25\%~ số test của đề ứng với ~100 < n \le 10^5.~

• Có ~50\%~ số test của đề ứng với ~10^5 < n \le 10^{18}.~