24962번 - It’s Surely Complex 다국어

문제

As you know, a complex number is often represented as the sum of a real part and an imaginary part. 3ドル + 2i$ is such an example, where 3ドル$ is the real part, 2ドル$ is the imaginary part, and $i$ is the imaginary unit.

Given a prime number $p$ and a positive integer $n,ドル your program for this problem should output the product of all the complex numbers satisfying the following conditions.

• Both the real part and the imaginary part are non-negative integers less than or equal to $n$.
• At least one of the real part and the imaginary part is not a multiple of $p$.

For instance, when $p = 3$ and $n = 1,ドル the complex numbers satisfying the conditions are 1ドル$ ($= 1 + 0i$), $i$ ($= 0 + 1i$), and 1ドル + i$ ($= 1 + 1i$), and the product of these numbers, that is, 1ドル × i × (1 + i)$ is $-1 + i$.

입력

The input consists of a single test case of the following format.

$p ,円 n$

$p$ is a prime number less than 5ドル × 10^5$. $n$ is a positive integer less than or equal to 10ドル^{18}$.

출력

Output two integers separated by a space in a line. When the product of all the complex numbers satisfying the given conditions is $a + bi,ドル the first and the second integers should be $a$ modulo $p$ and $b$ modulo $p,ドル respectively. Here, $x$ modulo $y$ means the integer $z$ between 0ドル$ and $y - 1,ドル inclusive, such that $x - z$ is divisible by $y$.

As exemplified in the main section, when $p = 3$ and $n = 1,ドル the product to be calculated is $-1 + i$. However, since $-1$ modulo 3ドル$ is 2ドル,ドル 2ドル$ and 1ドル$ are displayed in Sample Output 1.

제한

힌트