27877번 - 제곱수 덱 2

문제

1ドル$ 이상 $N$ 이하의 정수가 순서대로 적힌 $N$장의 카드가 있다. 각각의 카드는 초기에 자기 자신만으로 이루어진 덱이다.

와파스는 덱을 합칠 때마다 종이에다 수를 적는다. 처음에는 종이에 1ドル$이 적혀있다.

와파스는 다음 규칙을 따라 두 덱을 골라 하나의 덱으로 합친다.

• 두 덱을 합치기 전, 두 덱에서 카드를 각각 한 장씩 뽑는다.
• 뽑은 두 카드에 적힌 수를 $a,ドル $b$라고 했을 때, $a+b$가 반드시 제곱수여야 한다. 이러한 카드를 뽑는 것이 불가능하다면 이 두 덱은 합칠 수 없다.
• 두 덱을 하나로 합친 후에는 종이에 $|a - b|$를 적는다.

$N$장의 카드를 하나의 덱으로 합친 후, 와파스는 종이에 적힌 $N$개의 수를 모두 곱한 값인 $x$를 구한다.

와파스는 $x$의 값을 최소로 하여 덱을 모두 합치고 싶어한다. 와파스를 위해 $x$의 최솟값을 구해보자.

입력

양의 정수 $N$이 주어진다. $(1 \le N \le 10^{14})$

출력

$x$의 최솟값을 998ドル,244円,353円$로 나눈 나머지를 출력한다.

만약 $N$장의 카드를 하나의 덱으로 합칠 수 없다면 -1을 출력한다.

제한

힌트