결함 팩토리얼

자연수의 팩토리얼은 그 수 이하의 모든 양의 정수를 곱한 값이다. 예를 들어 $4$의 팩토리얼은 $1 \times 2 \times 3 \times 4 = 24$이다. 길이가 $n$인 결함 팩토리얼은 $n$의 팩토리얼과 같은 형태이지만, 곱해지는 정수 중 정확히 하나가 원래 값보다 작다. 작아진 자리의 값도 $1$ 이상이다. 예를 들어 $1 \times 2 \times 2 \times 4 = 16$은 길이가 $4$인 결함 팩토리얼이다.

길이 $n$, 소수인 나눗수 $p$, 목표 나머지 $r$가 주어진다. 길이가 $n$이고 $p$로 나눈 나머지가 $r$인 결함 팩토리얼을 찾아라.

첫째 줄에 결함 팩토리얼의 길이 $n$, 소수인 나눗수 $p$, 목표 나머지 $r$가 공백으로 구분되어 주어진다 ($2 \le n \le 10^{18}$, $2 \le p < 10^7$, $0 \le r < p$). $p$는 소수이다.

조건을 만족하는 결함 팩토리얼이 없으면 -1 -1을 출력한다. 있으면 결함이 있는 자리의 번호 $k$와 그 자리의 값 $v$를 공백으로 구분해 출력한다 ($2 \le k \le n$, $1 \le v < k$).

답이 여러 개이면 사전순으로 가장 작은 $(k, v)$를 출력한다. 즉 $k$가 가장 작은 답을 고르고, 그런 답이 여러 개이면 그중 $v$가 가장 작은 답을 고른다.

첫 번째 예제의 답은 결함 팩토리얼 $1 \times 2 \times 2 \times 4 = 16$을 나타낸다. $16$을 $5$로 나눈 나머지는 $1$이다.