An interesting counting problem related to square product K

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

Note

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

Test 2

Input

10 2

Output

Note

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

Test 3

Input

27 3

Output

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

Không có bình luận nào.