열대 식물원(Tropical Garden) timer 5초 memory 256MB

식물학자 철수는 여러 반의 학생들과 함께 태국 최대의 식물원을 방문하기로 하였다.

이 넓은 식물원은 N(0 ~ N-1)개의 연못과 M개의 산책로로 구성되어 있다.

각 산책로는 서로 다른 두 연못을 연결하며, 양방향으로 모두 이동하는 것이 가능하다.

어느 연못이든지 최소 하나의 산책로가 연결되어 있다. 이 산책로들에는 철수가 좋아하는 아름다운 식물들이 많이 있다.

같은 반의 학생들은 함께 이동하며, 각 반이 산책을 시작하는 연못은 서로 다를 수 있다.

철수는 아름다운 열대 식물들을 아주 좋아한다.

따라서, 철수와 각 반의 학생들은 어느 연못에서든 가장 아름다운 산책로를 선택하여 이용한다.

단, 그 산책로를 바로 직전에 이용한 경우에는 두 번째로 아름다운 산책로를 이용한다.

하지만, 현재 연못에 연결된 산책로가 단 하나뿐인 경우는 두 번째로 아름다운 산책로가 존재하지 않으므로 방금 사용한 산책로를 다시 이용하는 것을 허용한다. 철수는 식물학자이므로 두 산책로의 아름다운 정도가 같은 경우는 없다.

학생들은 식물에는 큰 관심이 없다.

학생들의 관심은 어떤 연못 P옆에 위치한 고급 식당에서 점심 식사를 하는 것이다.

철수는 각 반의 학생들이 정확히 K개의 산책로를 지난 다음 배가 고파질 것이라는 것을 알고 있다. 각 반 마다 K의 값은 다를 수 있다.

이 상황 하에서 철수는 각 반에 대해 정확히 K개의 산책로를 이용한 후 연못 P에 도착하는 방법의 수가 얼마나 많은지 알고 싶다.

각 반에 대한 상황을 정리하면 다음과 같다

● 각 반은 아무 연못에서나 출발할 수 있다. ● 산책로를 선택하는 규칙은 위의 설명과 같다. ● 각 반은 정확히 K개의 산책로를 이용한 다음에는 연못 P에 도착해야 한다. ● 산책로의 번호가 작을수록 더 아름답다는 것에 주의하자.     즉, 산책로 0 이 가장 아름다운 것이고, 산책로 1 이 그 다음으로 아름다운 것임을 알 수 있다.

각 반이 P로 가는 도중에 연못 P를 지나는 것도 가능하다. 그러나, 마지막에는 반드시 P에 도달하여야 한다.

해야 할 일

철수와 반 i의 학생들이 정확히 G[i]개의 산책로를 이용한 후 연못 P 에 도달할 수 있는 모든 가능한 서로 다른 경로들의 개수를 찾아야 한다.

예제 설명 

산책로의 번호가 작을 수록 더 아름답다는 것에 주의하자. 

즉, 산책로 0 이 가장 아름다운 것이고, 산책로 1 이 그 다음으로 아름다운 것임을 알수 있다. 

산책로의 개수가 3 이고 연못 0 에서 끝나면서 이동 규칙을 맊족하는 경로는 다음의 두가지 경우 밖에 없다. 

●​ 1 → 2 → 1 → 0 

●​ 5 → 4 → 3 → 0 

첫번째 경로는 연못 1 에서 시작한다. 

그 곳에서 가장 아름다운 산책로를 택하면 연못 2 로 가게 된다. 

연못 2 에서는 연못 1 로 가는 방법 밖에는 없다. 

이제 연못 1 에서는 방금 사용한 산책로를 제외하면 연못 0 으로 가는 산책로를 택하게 되어 목적지에 도착할 수 있다. 

따라서 2를 출력한다.

첫번째 반에 대해서 3 개의 산책로를 이용하여 연못 2 에 도착하는 방법은 하나 밖에 없으며 다음과 같다: 

1 → 0 → 1 → 2. 

두번째 반에 대해서 1 개의 산책로를 이용하여 연못 2 에 도착하는 방법은 다음의 두가지가 있다: 

3 → 2 와 4 → 2. 

따라서, 정확한 프로그램은 첫 번째 반에 대해 answer(1)을 호출하고 

두 번째 반에 대해 answer(2)를 호출해야 하며 정확한 호출 순서를 지켜야 핚다.