FoxAndMountain | Topcoder Archive

Problem Statement

Fox Ciel lives in a beautiful countryside. She loves climbing mountains. Yesterday, she went hiking in the mountains.

Her trip can be described as a sequence of (n+1) integers: h[0], h[1], ..., h[n]. These values represent altitudes visited by Fox Ciel during the trip, in order. Fox Ciel does not remember the precise sequence, but she remembers the following:

for each i, h[i] >= 0
h[0] = 0
h[n] = 0
for each i, abs(h[i+1]-h[i]) = 1

The last condition means that in each step the altitude of Fox Ciel either increased by 1, or decreased by 1. We will call the two types of steps "steps up" and "steps down", respectively. Steps up will be denoted 'U' and steps down will be denoted 'D'.

You are given the int n: the length of the trip. In addition to the length, Fox Ciel remembers some contiguous segment of her trip. You are given this segment as a String history. Each character of history is either 'U' or 'D'.

Let X be the number of different trips that match everything that Fox Ciel remembers. (Note that she may be mistaken, hence X may also be zero.) Compute and return the value (X modulo 1,000,000,009).

Definition

Class:: FoxAndMountain
Method:: count
Parameters:: int, String
Returns:: int
Method signature:: int count(int n, String history)
(be sure your method is public)

Constraints

n will be between 1 and 50, inclusive.
history will contain between 1 and n characters, inclusive.
Each character in history will be either 'U' or 'D'.

Examples

```
4
```
```
"UUDD"
```
```
Returns: 1
```
Fox Ciel remembers the entire history of her trip. The corresponding sequence of altitudes is {0, 1, 2, 1 ,0}.
```
4
```
```
"DUUD"
```
```
Returns: 0
```
Fox Ciel is mistaken. As n=4 and history="DUUD", the corresponding sequence of altitudes has to be {0, -1, 0, 1, 0}. However, all altitudes must be non-negative, so there is no matching trip.
```
4
```
```
"UU"
```
```
Returns: 1
```
The complete history must be "UUDD".
```
49
```
```
"U"
```
```
Returns: 0
```
It is not hard to see that for an odd n the answer has to be 0.
```
20
```
```
"UUUDUUU"
```
```
Returns: 990
```
```
30
```
```
"DUDUDUDUDUDUDUDU"
```
```
Returns: 3718
```
```
50
```
```
"U"
```
```
Returns: 946357703
```
Don't forget to use the modulo operations during the calculation.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.