Description

은비는 길을 걷다가 관광 명소인 쌍둥이 빌딩 숲을 보게 되었습니다. 쌍둥이 빌딩 숲은 일렬로 빌딩들이 줄지어 서있는 곳입니다.
쌍둥이 빌딩 숲에는 높이가 1부터 n까지 각각 2 채씩 총 2n채의 빌딩이 존재하기 때문에 그러한 이름이 붙게 되었으며, 같은 높이를 가지는 빌딩 사이에는 그보다 높은 빌딩이 존재하지 않습니다.

은비는 쌍둥이 빌딩 숲을 한쪽 측면에서(열 방향으로) 바라보고 있습니다. 이때 count 채의 빌딩이 구분되어 보였습니다.

은비의 세계는 안타깝게도 원근감이 존재하지 않지만, 다행히 서로 다른 높이를 가지는 빌딩들은 각각 고유한 색깔을 가지고 있어 어떤 빌딩이 다른 빌딩에 의해 전체가 가려지지 않는다면 볼 수 있습니다.

그림1.png
예를 들어 은비가 바라본 방향에서 가까운 빌딩부터 차례로 높이가 1,1,3,2,2,3 순이라면 높이가 2인 빌딩은 가려져서 보이지 않고, 높이가 1인 빌딩과 높이가 3인 빌딩만 구분되어 보입니다.

ncount가 주어졌을 때, 빌딩들이 배치될 수 있는 방법의 수를 return 하도록 solution 함수를 완성해주세요.


제한 사항
  • 1 ≤ n ≤ 100
  • 1 ≤ countn
  • 같은 높이의 빌딩은 같은 색이므로 서로 구분하지 않습니다.
  • 결과는 매우 클 수 있으므로 1,000,000,007 로 나눈 나머지를 return합니다.

입출력 예
n count result
3 1 8
3 2 6
3 3 1

입출력 예 설명

입출력 예 #1
가능한 방법마다 가장 가까운 빌딩부터 차례로 높이를 나열해보면 311223, 311322, 321123, 322113, 322311, 331122, 332112, 332211 으로 총 8 가지 방법이 있습니다.

입출력 예 #2
가능한 방법마다 가장 가까운 빌딩부터 차례로 높이를 나열해보면 113223, 113322, 211233, 221133, 223113, 223311 으로 총 6 가지 방법이 있습니다.

입출력 예 #1
가능한 방법마다 가장 가까운 빌딩부터 차례로 높이를 나열해보면 112233 으로 총 1 가지 방법이 있습니다.


※ 공지 - 2022년 12월 12일 문제 지문 수정 및 테스트 케이스가 추가되었습니다.

Result Stop
Result of [Run Test] or [Submit] will be displayed here