Kellie là một nữ rapper có rất nhiều fan hâm mộ tại Việt Nam, Obito cũng không phải là ngoại lệ. Vì sắp phải tham gia chương trình "Thách thức danh hài" nên Kellie đã nhờ Obito sáng tác cho mình 1 bài hát để chinh phục được nụ cười của ban giám khảo. Obito biết mình sẽ phải sáng tác không công cho Kellie nên anh quyết định đặt ra thử thách cho cô bằng cách ra 1 câu đố.

Obito định nghĩa 1 bộ số được gọi là "huhu" nếu bộ số đó có tích là 1 số chính phương. Ví dụ \(\{2, 2, 4\}, \{2, 8\}, \{9\}\) là các bộ số huhu, còn \(\{10, 8\}, \{9, 9, 2\}\) không phải là bộ số huhu.

Obito đưa cho Kellie \(N - 1\) số có giá trị lần lượt từ \(2\) đến \(N\), nhiệm vụ của Kellie là đếm số cách chọn ra \(K\) số trong \(N\) số đó sao cho \(K\) số đó là 1 bộ số huhu. Nếu trả lời đúng, Obito sẽ sáng tác 1 bài hát cho cô đi thi TTDH.

Vì Kellie chỉ biết rap nên các bạn thí sinh tham gia OLP Miền Trung Tây Nguyên hãy giúp cô giải bài toán này nhé!

TL;DR: Cho \(N-1\) số nguyên dương từ \(2\) đến \(N\) và 1 số \(K\). Bạn hãy đếm số cách chọn \(K\) số sao cho \(K\) số đó là bộ số huhu. 2 cách chọn gọi là khác nhau nếu có 1 số được chọn trong cách này không có trong cách kia.

Input

• Gồm 1 dòng duy nhất chứa 2 số nguyên dương lần lượt là \(N (2 \le N \le 10^5)\) và \(K (1 \le K \le 3)\)
  
  Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

• In ra số lượng số bộ số huhu có trong dữ liệu vào của chương trình.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(N \le 10^5, K = 1\)
• Subtask \(2\) (\(20\%\) số điểm): \(N \le 5 \times 10^3, K = 2\)
• Subtask \(3\) (\(20\%\) số điểm): \(N \le 5 \times 10^2, K = 3\)
• Subtask \(4\) (\(20\%\) số điểm): \(N \le 10^5, K = 2\)
• Subtask \(5\) (\(20\%\) số điểm): \(N \le 10^5, K = 3\)

Example

16 2

5

10 3

6