Stair Climbing Workout

Jungyu enjoys climbing stairs as exercise.

Jungyu makes $N$ moves on a staircase, and those moves are described by a sequence $H$ of length $N+1$. $H_0$ is his starting position and is always 0. $H_N$ is his final position and is also always 0. The value $H_i$ is the number of the stair he stands on after the $i$-th move, and every $i$ must satisfy $|H_{i+1} - H_i| = 1$ and $H_i \ge 0$. Each move goes exactly one stair up or one stair down, and he never steps below stair 0.

Jungyu records each day's workout as a string of length $N$. A move one stair up is written as U and a move one stair down is written as D. This string is called the workout string. Gangho tore up the record sheet, so only a contiguous piece of the workout string is left.

Given the remaining piece, write a program that counts the workout strings of length $N$ that contain the piece as a contiguous substring. Count distinct workout strings: a string is counted once even when the piece occurs in it at several positions. Gangho may have altered the piece, so the answer can be 0.

The first line contains $N$ ($1 \le N \le 100$).

The second line contains the remaining piece. The piece consists only of U and D, and its length is at least 1 and at most $N$.

Print the number of workout strings that satisfy the condition, modulo 1,000,000,009.