구름이는 구름카페를 운영하는 사장님이다. 구름카페에는 테이블이  격자 형태로 배열되어 있다. 한 줄에는 개의 테이블이 있고, 이러한 줄이 총 줄 있다.

기존에는 모든 테이블에 동시에 사람들이 앉을 수 있었다. 하지만 사람들 사이에서 소음으로 자주 다툼이 발생하자, 구름이는 테이블 간 거리두기를 시행해서 일부 테이블에서만 앉아서 커피를 마시거나 작업을 할 수 있도록 하려고 한다. 테이블 간 거리두기를 시행하게 되면 어떤 사람이 앉아있는 자리에서 앞뒤와 양옆으로 인접한 테이블에는 동시에 사람들이 앉을 수 없게 된다.

구름이는 거리두기 방식에 따라, 사람들이 앉을 수 있는 테이블에 스티커를 붙이기로 했다. 구름이는 충분히 많은 스티커를 가지고 있기 때문에 붙일 수 있는 스티커의 개수에는 제한이 없으며, 스티커를 하나도 붙이지 않을 수도 있다.

구름카페에 있는 테이블의 줄 수 이 주어졌을 때, 구름이가 테이블에 스티커를 붙일 수 있는 경우의 수를 구해보자. 단, 수가 너무 커질 수 있으므로 경우의 수를 로 나눈 나머지를 출력한다.

예제 설명

구름 카페의 한 줄에 나올 수 있는 스티커 배치의 경우의 수는 아래의 가지 이다. 스티커를 하나도 붙이지 않는 경우도 포함해야 함을 유의하라.

아래는 구름 카페에 두 줄의 테이블이 있을 때 스티커를 붙일 수 있는 경우의 수 중 일부이다.

입력

첫째 줄에 테이블의 줄 수를 의미하는 정수 이 주어진다.

출력

구름이가 테이블에 스티커를 붙일 수 있는 모든 경우의 수를 로 나눈 나머지를 출력한다.