수열의 합

2024년 2학기는 지금까지 MatKor Cup을 주도하던 동우, 재우, 종우를 비롯한 많은 사람의 마지막 학기이다. MatKor는 특별한 사건 없이 한 학기가 지나갔지만, 국가적으로 평화롭지 않았던 연말이 지나고 2025년이 되었다. 재우는 올해 1월 1일에도 떠오르는 태양을 보며 올해는 면허를 따야지 다짐한다.

재우는 2025년이 밝자 $2025=(1+2+3+\cdots +9)^2$이라는 사실에 매우 놀랐다. 심지어 $2025=1^3+2^3+3^3+\cdots +9^3$도 성립하는 것을 보고 재우는 매우 놀라 동우에게 말했다. 동우는 이를 보더니 두 식이 동치가 아니냐며 일침을 날렸다.

옆에서 이 모습을 지켜보던 마음씨 착한 도훈이는 재우를 위로하며, 재우에게 동우 몰래 $X^3$과 $3^X$을 이용한 해시 인증 체계를 만들자고 제안했다.

먼저 수열 $A$에 대해 함수 $T(A)$를 원소들의 세제곱의 합을 3의 거듭제곱 꼴로 취한 값으로 정의한다. 즉, 다음과 같다.

$T(A)=3^{\sum_{i=1}^N A_i^3}$

인증을 위해 먼저 개인키로 세 정수 $N$, $S$, $L$을 준비한다. 길이가 $N$이고, 모든 원소가 $0$ 이상 $L$ 이하의 정수이며, 모든 원소의 합이 $S$인 수열의 집합을 $\mathbb{A}(N,S,L)$라 하자. 즉, 다음과 같다.

$\mathbb{A}(N,S,L)=\left\{ A\in\mathbb{Z}_{L+1}^N \middle| \sum_{i=1}^N A_i=S \right\}$

해시 함수 $\mathbb{H}(N,S,L)$은 $\mathbb{A}(N,S,L)$의 모든 원소에 대한 $T$값의 합으로 정의한다. 즉, 다음과 같다. 만약 $\mathbb{A}(N,S,L)=\varnothing$이라면 $\mathbb{H}(N,S,L)=0$이다.

$\mathbb{H}(N,S,L)=\sum_{A\in\mathbb{A}(N,S,L)} T(A)$

재우와 도훈이는 새로운 인증 요청이 들어오면 $\mathbb{H}$로 계산한 해시값을 비교해 인증할 수 있다. 그리고 C++을 좋아하는 두 사람은 큰 수 연산이 귀찮아서 해시값의 모듈로를 비교하려 한다. 즉, 올바른 키가 $(N,S,L)$이고 입력된 키가 $(N^\prime,S^\prime,L^\prime)$일 때, $P=998\,244\,353$에 대해 $\mathbb{H}(N,S,L)\equiv\mathbb{H}(N^\prime,S^\prime,L^\prime)\pmod P$인지 검사해 성립하면 올바른 인증이라고 판단한다.

재우는 이 해시가 안전한지 확인하려고 해시 충돌 가능성을 알아보려 한다. 즉, $(N,S,L)\ne(N^\prime,S^\prime,L^\prime)$이지만 $\mathbb{H}(N,S,L)\equiv\mathbb{H}(N^\prime,S^\prime,L^\prime)\pmod P$가 성립하는 경우가 있는지 알아보려 한다. 재우는 특히 키 $(N,S,L)$가 주어질 때, $\mathbb{H}(N,S,L)\equiv\mathbb{H}(1,X,X)\pmod P$를 만족하는 음이 아닌 정수 $X$를 찾고 싶다.

재우를 도와 주어진 $(N,S,L)$에 대해 해시 충돌을 일으킬 수 있는 $(1,X,X)$가 있다면 찾아보자.

첫 번째 줄에 수열의 길이 $N(2\le N\le 10^{18})$, 수열의 합 $S(0\le S\le 2\cdot 10^5)$, 원소의 최댓값 $L(0\le L\le S)$이 공백으로 구분되어 주어진다.

첫 번째 줄에 주어진 조건을 만족하는 음이 아닌 정수 $X$가 존재하면 $X$의 최솟값을, 존재하지 않으면 -1을 출력한다.