An interesting counting problem related to square product K

Tác giả:

Dạng bài

Ngôn ngữ cho phép

Assembly, Awk, C, C#, C++, Clang, Cobol, D, ~~Groovy~~, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, Output, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, ~~Swift~~

Điểm: 1600 (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 (4)

Tải bình luận...