34982번 - 룩 vs 폰

문제

대신이와 오량이는 오늘도 한판 대결을 펼치고 있다. 이번에는 특별한 규칙으로 진행되는 '룩 vs 폰' 게임을 하기로 했다.

게임은 8ドル \times K$ 크기의 체스판에서 진행된다.

• 2ドル$행 1ドル$열부터 2ドル$행 $N$열까지 대신이의 폰이 한 칸에 1ドル$개씩 총 $N$개가 놓여있다.
• 8ドル$행 $M$열에 오량이의 룩 1ドル$개가 놓여있다.

플레이어는 번갈아 가며 자신의 기물 1ドル$개를 골라 체스판에서 벗어나지 않게 행마법을 따라 움직인다. 행마법은 노트를 참고하자.

게임의 승리 조건은 다음과 같다.

• 대신이의 어떤 폰이라도 8ドル$행에 도달하거나, 대신이의 폰이 오량이의 룩을 잡으면 대신이가 승리한다.
• 오량이의 룩이 대신이의 폰을 잡고, 돌아오는 대신이의 차례에 대신이가 오량이의 룩을 잡을 수 없다면 오량이가 승리한다.

(그림 1) 대신이의 폰이 8ドル$행에 도달했다. 따라서 대신이가 승리한다.

(그림 2) 대신이의 폰이 오량이의 룩을 잡았다. 따라서 대신이가 승리한다.

(그림 3) 돌아오는 대신이의 차례에 대신이는 오량이의 룩을 잡을 수 없다. 따라서 오량이가 승리한다.

하지만 오량이가 너무 유리하다고 느낀 대신이는 다음 규칙을 추가했다.

• 오량이의 룩은 기본적으로 8ドル$행에 머물러야 하며, 대신이의 폰을 잡을 때만 8ドル$행을 벗어날 수 있다.

(그림 4) 대신이의 폰을 잡는 움직임이다. 따라서 가능한 수이다.

(그림 5) 대신이의 폰을 잡는 움직임이 아니다. 따라서 불가능한 수이다.

모든 플레이어는 가장 빠르게 승리하기 위해 최선을 다하며, 만약 승리할 수 없다면 최대한 늦게 지도록 행동한다.

대신이는 오량이에게 선공을 양보했다. 양쪽 모두 최선을 다할 때, 오량이가 승리하기 위해 룩을 움직여야 하는 최소 횟수를 구해주자!

입력

첫번째 줄에 세 정수 $N, M, K$가 공백으로 구분되어 주어진다. $(1 \leq N,M \leq K;$ 1ドル \leq K \leq 10^{9})$

출력

첫번째 줄에 오량이가 승리하기 위해 룩을 움직여야 하는 최소 횟수를 998ドル,244円,353円$로 나눈 나머지를 출력한다.

만일 최선을 다해도 오량이가 이길 수 없다면, 대신 -1을 출력한다.

제한

노트

각 기물의 행마법은 체스와 동일하며, 아래와 같다.

• 대신이의 폰은 2ドル$행에 있을 경우 행이 증가하는 방향으로 1ドル$칸 또는 2ドル$칸 이동할 수 있고, 그 외에는 1ドル$칸만 이동한다. 전진 방향의 대각선에 오량이의 룩이 있으면 룩을 잡으며 그 위치로 이동할 수 있다.

빨간색 칸은 공격 범위, 화살표는 이동 범위를 뜻한다.

• 오량이의 룩은 같은 행의 다른 칸 또는 같은 열의 다른 칸으로 이동할 수 있으며, 이동한 칸에 대신이의 폰이 있으면 폰을 잡을 수 있다.

화살표는 이동 범위를 뜻한다. 공격 범위는 이동 범위와 같다.