시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 260 102 79 37.619%

문제

기문이는 특이한 외계 생물을 한 마리 발견하였다. 발견될 때에는 갓 태어난 상태였다. 이 생물은 태어난 지 하루가 지나면 정확히 두 명의 새끼를 낳는데, 한번 새끼를 낳고 나면 그 이후로는 새끼를 낳지 못한다. 따라서 발견한 지 0일째에는 1마리, 1일째에는 1 + 2 = 3마리, 2일째에는 1 + 2 + 4 = 7마리가 된다. 즉, H일째에 2H+1 - 1마리가 되는 것이다.

기문이는 H일째에 이 외계 생물들에게 번호를 붙이려고 하였다. H일째에는 총 2H+1 - 1마리이므로 1번부터 2H+1 - 1번까지를 한 번씩만 사용하여 번호를 붙이려고 하는데, 부모의 번호는 자식의 번호보다 항상 작게 하려 한다. 번호를 붙일 수 있는 경우의 수를 구하시오.

입력

첫 줄에 정수 H (0 ≤ H ≤ 10)가 입력으로 주어진다. 이는 발견한 지 H일째임을 의미한다.

출력

번호를 붙일 수 있는 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력 1

1

예제 출력 1

2

예제 입력 2

2

예제 출력 2

80

힌트

1 일째의 경우 번호를 붙일 방법은 다음과 같이 2가지가 있다.