An interesting counting problem related to square product K

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
SPyofgame , SPectiar2k
Dạng bài
Điểm: 400 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Given \(n, k (1 \leq k \leq n \leq 10^6)\), count the number of arrays \(a[]\) of size \(k\) satisfies:

  • \(1 \leq a_1 < a_2 < \dots < a_k \leq n\).
  • \(a_i \times a_j\) is a perfect square \(\forall 1 \leq i < j \leq k\).

Since the result can be large, output it under modulo \(10^9 + 7\).

Example

Test 1

Input 
2 1
Output 
2
Note

There are \(2\) satisfied array of size \(1\): {\(1\)}, {\(2\)}.

Test 2

Input 
10 2
Output 
4
Note

There are \(4\) satisfied array of size \(2\): {\(1, 4\)}, {\(1, 9\)}, {\(2, 8\)}, {\(4, 9\)}.

Test 3

Input 
27 3
Output 
12
Note

There are \(12\) satisfied array of size \(3\): {\(1, 4, 9\)}, {\(1, 4, 16\)}, {\(1, 4, 25\)}, {\(1, 9, 16\)}, {\(1, 9, 25\)}, {\(1, 16, 25\)}, {\(2, 8, 18\)}, {\(3, 12, 27\)}, {\(4, 9, 16\)}, {\(4, 9, 25\)}, {\(4, 16, 25\)}, {\(9, 16, 25\)}.

Bình luận