시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 386 | 160 | 127 | 41.368% |
기문이는 특이한 외계 생물을 한 마리 발견하였다. 발견될 때에는 갓 태어난 상태였다. 이 생물은 태어난 지 하루가 지나면 정확히 두 명의 새끼를 낳는데, 한번 새끼를 낳고 나면 그 이후로는 새끼를 낳지 못한다. 따라서 발견한 지 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
2
2
80
1 일째의 경우 번호를 붙일 방법은 다음과 같이 2가지가 있다.
University > 서강대학교 > 2016 Sogang Programming Contest > Master G번