13438번 - 계단 오르기 운동

준규는 계단 오르기 운동을 즐겨한다.

준규는 계단을 총 N번 이동하며, 그 이동은 길이가 N+1인 수열 H로 나타낼 수 있다.

H₀은 처음 준규의 위치이며, 항상 0이다. H_N은 준규의 마지막 위치이며 항상 0이다. 그 사이 값 H_i는 준규가 i번째 이동에서 몇 번째 계단에 있었는지를 나타내며, |H_i+1 - H_i| = 1을 만족해야 한다. 또, 모든 H_i는 0보다 크거나 같아야 한다. 즉, 준규는 계단을 한 칸 올라가거나 내려갈 수 있다.

준규는 자신이 한 운동의 방법을 매일 적어놓는다. 하루의 운동은 길이가 N인 문자열로 나타낼 수 있으며, 계단을 한 칸 올라간 것은 U, 내려간 것은 D로 나타낸다. 이 문자열을 운동 문자열이라고 한다. 하지만, 운동 문자열을 적어놓은 종이를 강호가 찢어버렸기 때문에, 준규는 지금 운동 문자열의 연속된 일부분을 가지고 있다.

준규의 운동 문자열의 연속된 일부분이 주어졌을 때, 길이가 N인 운동 문자열을 만들 수 있는 방법의 수를 구하는 프로그램을 작성하시오. 강호가 운동 문자열을 수정했을 수도 있기 때문에, 방법의 수는 0이 될 수도 있다.

첫째 줄에 N (1 ≤ N ≤ 100)이 주어지고, 둘째 줄에 운동 문자열의 연속된 일부분이 주어진다.

첫째 줄에 운동 문자열을 만들 수 있는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.