문제

구름이는 보드 게임을 하고 있다. 보드 게임은 번 칸부터 번 칸까지 개의 칸이 일렬로 놓인 보드와 말 하나로 구성되어 있다. 처음에는 시작 지점인 번 칸에 구름이의 말을 두고, 말을 도착 지점인 번 칸까지 옮기는 것이 게임의 목표이다.

말을 옮길 때는 다음 규칙을 따라야 한다. 구름이는 말을 한 번 옮길 때 항상 칸 또는 칸 앞으로만 옮길 수 있으며, 보드 밖으로 말을 옮길 수는 없다.

구름이가 규칙에 따라서 시작 지점에서 도착 지점까지 말을 옮길 수 있는 방법의 개수를 출력하시오.

입력

첫째 줄에 이 주어진다.

출력

구름이가 번 칸에서 출발해서 번 칸으로 이동할 수 있는 방법의 개수를 로 나눈 나머지를 출력하시오.