대수

정수 $n$, $m$, $k$가 주어질 때, 다음 조건을 모두 만족하는 정수 쌍 $(a, b)$의 개수를 구하라.

• $|a|, |b| \leq m$
• $a, b \in \mathbb{Z}$, 즉 $a$와 $b$는 정수이다
• $|S| = k$. 여기서 $S$는 방정식 $x^n + a \cdot x + b = 0$의 유리근 집합이고, $|S|$는 $S$의 원소 개수이다. 즉, 이 방정식의 서로 다른 유리수 해 $x$가 정확히 $k$개 있어야 한다.

$x$가 유리수라는 것은 $q \neq 0$인 정수 $p$, $q$가 존재하여 $x = \frac{p}{q}$로 쓸 수 있다는 뜻이다.

여러 개의 테스트 케이스가 주어지며, 입력은 파일 끝(EOF)에서 끝난다. 각 테스트 케이스의 첫 줄에는 정수 $n$, $m$, $k$가 주어진다.

각 테스트 케이스마다 조건을 만족하는 쌍의 개수를 정수 하나로 출력한다.

• $1 \leq n, m, k \leq 5 \times 10^5$
• 각 입력에서 $m$의 합은 $5 \times 10^5$을 넘지 않는다.

첫 번째 테스트 케이스에서는 방정식 $x^2=0$만이 유리근을 하나 가진다.

두 번째 테스트 케이스에서는 다음 7개의 방정식이 각각 서로 다른 유리근을 두 개씩 가진다: $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$.