Cho số nguyên dương ~ X ~ và ~ n ~. Hãy đếm số cách phân tích ~ X ~ thành ~ a_1^n + a_2^n + ⋯ + a_k^n ~, trong đó ~ 0 < a_1 < a_2 < ⋯ < a_k ~

Dữ liệu vào

• Dòng đầu ghi số nguyên dương ~ X ~ ~ (1 ≤ X ≤ 1000) ~
• Dòng thứ 2 ghi số nguyên dương ~ n ~ ~ (2 ≤ n ≤ 10) ~

Kết quả

Một số nguyên duy nhất là số cách theo yêu cầu đề bài

Ví dụ:

Input 1

100
2 

Output 1

3