31111번 - Algebra 다국어

문제

Given three integers $n,ドル $m,ドル $k,ドル find the number of pairs $(a, b)$ where

• $|a|, |b| \leq m,ドル
• $a, b \in \mathbb{Z},ドル i.e., $a$ and $b$ are integers,
• $|S| = k$ where $S$ be the set of rational roots of the equation $x^n + a \cdot x + b = 0,ドル and $|S|$ is the size of $S$. In particular, there exists exactly $k$ distinct rational numbers $x$ which solve the last equation.

Note: $x$ is a rational number if and only if there exists two integers $p$ and $q$ ($q \neq 0$) where $x = \frac{p}{q}$.

입력

The input consists of several test cases terminated by end-of-file. For each test case,

The first line contains three integers $n,ドル $m$ and $k$.

출력

For each test case, output an integer which denotes 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$