문제 설명
루루는 다음과 같은 방법으로 책상들을 이어 붙여 모든 모둠이 소통할 수 있도록 하고 싶다.
(1) 책상 방향은 돌리지 않는다.
(2) 2개 이상의 책상을 좌우로 이어 붙여 하나의 모둠을 만든다.
(3) 한 줄에 1개의 모둠만 만든다.
(4) 각 모둠의 책상들 중 1면 이상을 앞 줄과 뒷 줄에 붙여 모둠끼리 소통할 수 있게 한다.
예를 들어, 4개의 책상을 사용하면 다음과 같은 4가지 방식의 책상 배치를 만들 수 있다.
책상의 개수(n)가 주어질 때, 루루가 만들 수 있는 모둠 배치의 가짓수를 출력하시오.
(1) 책상 방향은 돌리지 않는다.
(2) 2개 이상의 책상을 좌우로 이어 붙여 하나의 모둠을 만든다.
(3) 한 줄에 1개의 모둠만 만든다.
(4) 각 모둠의 책상들 중 1면 이상을 앞 줄과 뒷 줄에 붙여 모둠끼리 소통할 수 있게 한다.
예를 들어, 4개의 책상을 사용하면 다음과 같은 4가지 방식의 책상 배치를 만들 수 있다.
책상의 개수(n)가 주어질 때, 루루가 만들 수 있는 모둠 배치의 가짓수를 출력하시오.
입력 설명
n이 입력된다. [2 <= n <= 100]
출력 설명
모둠을 배치할 수 있는 경우의 수를 출력한다.
단, 경우의 수가 10,000,000 이상일 경우에는 10,000,000으로 나눈 나머지를 출력한다.
단, 경우의 수가 10,000,000 이상일 경우에는 10,000,000으로 나눈 나머지를 출력한다.
입력 예시 Copy
4
출력 예시 Copy
4