계단 오르기 운동

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

준규는 계단에서 총 $N$번 이동하고, 그 이동은 길이가 $N+1$인 수열 $H$로 나타낼 수 있다. $H_0$은 준규의 처음 위치이고 항상 0이다. $H_N$은 준규의 마지막 위치이고 역시 항상 0이다. 중간 값 $H_i$는 $i$번째 이동을 마친 뒤 준규가 서 있는 계단 번호이며, 모든 $i$에 대해 $|H_{i+1} - H_i| = 1$과 $H_i \ge 0$을 만족해야 한다. 즉 준규는 한 번에 계단을 한 칸 올라가거나 한 칸 내려가고, 0번 계단보다 아래로는 내려가지 않는다.

준규는 하루 운동을 길이 $N$인 문자열로 기록한다. 한 칸 올라간 이동은 U, 한 칸 내려간 이동은 D로 적고, 이 문자열을 운동 문자열이라고 부른다. 그런데 강호가 기록지를 찢어버려서 준규에게는 운동 문자열의 연속된 일부분만 남았다.

남은 조각이 주어질 때, 그 조각을 연속된 부분 문자열로 포함하는 길이 $N$의 운동 문자열이 몇 개인지 구하는 프로그램을 작성하시오. 서로 다른 운동 문자열의 개수를 세며, 한 운동 문자열 안에서 조각이 여러 위치에 나타나도 한 번만 센다. 강호가 조각을 고쳐 썼을 수도 있으므로 답이 0일 수도 있다.

첫째 줄에 $N$이 주어진다 ($1 \le N \le 100$).

둘째 줄에 남은 조각이 주어진다. 조각은 U와 D로만 이루어져 있고, 길이는 1 이상 $N$ 이하이다.

첫째 줄에 조건을 만족하는 운동 문자열의 개수를 1,000,000,009로 나눈 나머지를 출력한다.