외계 생물

기문이가 특이한 외계 생물 한 마리를 발견했다. 발견했을 때는 갓 태어난 상태였다. 이 생물은 태어난 지 하루가 지나면 정확히 두 마리의 새끼를 낳고, 한 번 낳은 뒤로는 다시 새끼를 낳지 않는다. 한 부모가 낳은 두 새끼는 첫째와 둘째로 구별한다.

그래서 발견한 지 0일째에는 1마리, 1일째에는 $1 + 2 = 3$마리, 2일째에는 $1 + 2 + 4 = 7$마리가 된다. 즉 $H$일째에는 $2^{H+1} - 1$마리다.

기문이는 $H$일째에 이 생물들에게 번호를 붙이려 한다. $1$번부터 $2^{H+1} - 1$번까지를 한 번씩만 써서 모든 개체에 번호를 붙이되, 부모의 번호는 항상 자식의 번호보다 작아야 한다. 번호를 붙이는 경우의 수를 구하시오.

첫 줄에 정수 $H$ ($0 \le H \le 10$)가 주어진다. 발견한 지 $H$일째라는 뜻이다.

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

$H = 1$이면 개체는 부모 한 마리와 새끼 두 마리로 모두 3마리다. 부모의 번호가 두 자식보다 작아야 하므로 부모는 반드시 1번이고, 남은 2번과 3번을 첫째와 둘째에게 배정하는 순서가 두 가지다. 그래서 답은 2다.