Algebra

Given three integers $n$, $m$, and $k$, find the number of pairs $(a, b)$ that satisfy all of the following conditions.

• $|a|, |b| \leq m$
• $a, b \in \mathbb{Z}$, that is, $a$ and $b$ are integers
• $|S| = k$, where $S$ is the set of rational roots of the equation $x^n + a \cdot x + b = 0$ and $|S|$ is the size of $S$. In other words, the equation has exactly $k$ distinct rational numbers $x$ as solutions.

A number $x$ is rational if and only if there exist integers $p$ and $q$ with $q \neq 0$ such that $x = \frac{p}{q}$.

The input consists of several test cases, terminated by end-of-file. The first line of each test case contains three integers $n$, $m$, and $k$.

For each test case, output one integer, the number of pairs.

• $1 \leq n, m, k \leq 5 \times 10^5$
• In each input, the sum of $m$ does not exceed $5 \times 10^5$.

For the first test case, only the equation $x^2=0$ has one rational root.

For the second test case, each of the following 7 equations has two distinct rational roots: $x^2-2x=0$, $x^2-x=0$, $x^2-x-2=0$, $x^2-1=0$, $x^2+x=0$, $x^2+2x=0$, $x^2+x-2=0$.