강을 경계로 비토와 스턴 마을이 있었다.

두 마을 사이에는 아무런 접촉도 없이 서로 고립되어 생활을 하고 있었다.

그러던 중 스턴 마을에서는 스파이를 비토 마을에 보내기로 결정하였다.

그러나 강을 건너 비토 마을로 들어갈 수 있는 배가 한척 밖에 없다.

또한 이 배는 특이한 점을 가지고 있었다. 배는 항상 S명이 탑승해야 하며 비토 마을에 도착하면

반드시 한 명만이 비토 마을에 남고 나머지는 다시 스턴 마을로 돌아와 S명을 태우고 다시 비토 마을로 갈 수 있다.

다시 말하면 이 배는 다음과 같은 방법으로 운행된다.

· 처음 스턴 마을을 떠날 때 스파이 1, 2, ... , S명을 싣고 간다.

그 중 한명이 비토 마을에 내리고 나머지 S-1명이 스턴 마을로 되돌아온다. · 두 번째 스턴 마을을 떠날 때 스파이 S+1, S+2, ... , 2S와 되돌아 온 S-1명의 스파이를 싣고 비토 마을로 향한다.

그들 중 한 명이 비토 마을에 내리고 나머지 2S-2명의 스파이 턴 마을로 되돌아온다. · 세 번째는 스파이 2S+1, 2S+2, ... , 3S와 되돌아온 2S-2명의 스파이가 비토 마을로 향한다.

그들 중 한 명이 비토 마을에 내린다.

이와 같이 계속한다. N번 비토 마을에 다녀온 후,

파견된 스파이 N명을 구성하는 방법의 수를 모두 구하는 프로그램을 작성하시오.

스파이 보내기 timer 1s memory 128MB

스파이 보내기 1s 128MB