문제

왓슨과 릿카는 오늘도 한판 승부를 벌이고 있다. 이번에는 특별한 규칙으로 진행되는 '룩 vs 폰' 게임을 하기로 했다.

게임은 크기의 체스판에서 진행된다.

• 행 열부터 행 열까지 왓슨의 폰이 한 칸에 개씩 총 개가 놓여있다.
• 행 열에 릿카의 룩 개가 놓여있다.

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

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

• 왓슨의 어떤 폰이라도 행에 도달하거나, 왓슨의 폰이 릿카의 룩을 잡으면 왓슨이 승리한다.
• 릿카의 룩이 왓슨의 폰을 잡고, 돌아오는 왓슨의 차례에 왓슨이 릿카의 룩을 잡을 수 없다면 릿카가 승리한다.

(그림1) 왓슨의 폰이 8행에 도달했다. 따라서 왓슨이 승리한다.

(그림2) 왓슨의 폰이 릿카의 룩을 잡았다. 따라서 왓슨이 승리한다.

(그림3) 돌아오는 왓슨의 차례에 왓슨은 릿카의 룩을 잡을 수 없다. 따라서 릿카가 승리한다.

하지만 릿카가 너무 유리하다고 느낀 왓슨은 다음 규칙을 추가했다.

• 릿카의 룩은 기본적으로 8행에 머물러야 하며, 폰을 잡기 위해서만 8행을 벗어날 수 있다.

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

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

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

왓슨은 릿카에게 선공을 양보했다. 양쪽 모두 최선을 다할 때, 릿카가 승리하기 위해 룩을 움직여야 하는 최소 횟수를 구해보자!

입력

첫번째 줄에 세 정수 가 공백으로 구분되어 주어진다.

출력

릿카가 승리하기 위해 룩을 움직여야 하는 최소 횟수를 로 나눈 나머지를 출력한다.

만일 최선을 다해도 릿카가 이길 수 없다면, 을 출력한다.

노트

예제1에서 가능한 움직임 중 하나이다.

예제2에서 가능한 움직임 중 하나이다.

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

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

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

• 릿카의 룩은 같은 행의 다른 칸 또는 같은 열의 다른 칸으로 이동할 수 있으며, 이동한 칸에 왓슨의 폰이 있으면 폰을 잡을 수 있다.

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