엘리베이터 timer 1s memory - MB

어느날 경완이는 역삼동에 있는 스타타운이라는 고층 건물에 가게 되었는데, 그곳의 엘리베이터들은 다른 엘리베이터들과는 이상하게 운행되고 있었다. 해당 건물의 층 수는 58층이고, 총 2개의 엘리베이터가 운영되고 있었다. 낮게 올라가 있는 엘리베이터가 x층에서 멈추게 될 경우 높이 올라가 있는 엘리베이터는 동시에 x+1층에서 멈추게 된다. 만약 엘리베이터 하나가 1, 3, 5, ..., 57 층에서 멈출 경우, 다른 엘리베이터는 2, 4, 6, ..., 58 층에서 멈추게 된다.

경완이는 이러한 엘리베이터의 운행방식에 흥미를 가졌고, 이를 일반화 하여 N개의 엘리베이터가 운행되고 층의 숫자가 H일 경우에 가능한 운행방법의 수를 알아내고자 하는데, 다음의 규칙을 만족해야한다.

각 층마다 정확히 한개의 엘리베이터가 멈추어야 한다. 임의의 2개의 엘리베이터 사이의 운행 거리는 변하지 않는 정수여야 한다. 다시 말해서 엘리베이터 A와 B가 있을 때 B가 x+d층에서 멈출 경우는 A는 x 층에서 멈춰야 한다는 것이다. 만약 x+d층이 존재하지 않을 경우 엘리베이터는 x층에서 멈춰서는 안된다.

다음의 경우를 만족하면 두 운행방법은 서로 다르다고 간주한다. 가장 낮은 위치의 엘리베이터가 1층에 있을 때, i번째에서 운행을 시작하는 엘리베이터가 존재하고 다른 경우에 i번째에서 운행을 시작하는 경우가 존재하지 않을 경우 다른 경우로 간주한다.