----
Statement:
Given two integer $$$n, k, p$$$, $$$(1 \leq k \leq n < p)$$$.
Count the number of array $$$a[]$$$ of size $$$k$$$ that satisfied
- $$$1 \leq a_1 < a_2 < \dots < a_k \leq n$$$
- $$$a_i \times a_j$$$ is perfect square $$$\forall 1 \leq i < j \leq n$$$
Since the number can be big, output it under modulo $$$p$$$.
----
Solve for k = 1
The answer just simply be $$$n$$$
----
Solve for k = 2
We need to count the number of pair $$$(a, b)$$$ that $$$1 \leq a < b \leq n$$$ and $$$a \times b$$$ is perfect square
Every positive integer $$$x$$$ can be represent uniquely as $$$x = u \times p^2$$$ for some positive integer $$$u, p$$$ and $$$u$$$ as small as possible ($$$u$$$ is squarefree number)
Let represent $$$x = u \times p^2$$$ and $$$y = v \times q^2$$$ (still, minimum $$$u$$$, $$$v$$$ ofcourse)
We can easily proove that $$$x \times y$$$ is a perfect square if and if only $$$u = v$$$
So for a fixed squarefree number $$$u$$$. You just need to count the number of ways to choose $$$p^2$$$
Therefore the answer just simply be
----
Solve for general k
Using the same logic above, we can easily solve the problem with combinatorics
----
A better solution for k = 2
Let $$$f(n)$$$ is the number of $$$(a, b)$$$ that $$$1 \leq a \leq b \leq n$$$ and $$$(a, b, n)$$$ is a three-term geometric progression
Let $$$F(N) = \overset{n}{\underset{x=1}{\Large \Sigma}} f(x)$$$
