Problem Statement
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
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.
42
"DDDDUUUUDDDDDUDDDDDDDUUDDUDDDD"
Returns: 0
48
"DDDDDDD"
Returns: 11210520
11
"D"
Returns: 0
38
"UUUUUUUUUDUUU"
Returns: 657800
42
"DDUUU"
Returns: 901366256
9
"D"
Returns: 0
32
"UDDDUU"
Returns: 11386309
20
"DDDDUDUD"
Returns: 715
30
"D"
Returns: 9694845
6
"U"
Returns: 5
14
"U"
Returns: 429
17
"UD"
Returns: 0
50
"DDDUDUDDDUUUUUUUDDUUUUDDU"
Returns: 230230
2
"D"
Returns: 1
4
"D"
Returns: 2
44
"DUDUD"
Returns: 632106360
48
"UDUD"
Returns: 922505942
30
"DUU"
Returns: 9678461
32
"DUD"
Returns: 35047098
22
"DUDDDDUDDUDUUDDD"
Returns: 1
32
"UUDDUDDDUUDDUUUDUUDDUDUDUUDUUUUU"
Returns: 0
28
"DDDDDDDDDDDDD"
Returns: 15
50
"DDDUDDDDDDDDD"
Returns: 414926201
50
"DDDDDDDUUUUDDDDDDDDDDDUDD"
Returns: 65780
14
"DDDDDDD"
Returns: 1
40
"DDUDUDUDDDD"
Returns: 86384698
28
"DDDDDDDDDDD"
Returns: 680
40
"DDDUDUUDUUUU"
Returns: 20026662
49
"DUDUDUUDDDDDUUDUDUDDDDDDDDDDUDDDDDDDDUDUDD"
Returns: 0
22
"DUDUDDUUDDD"
Returns: 495
12
"DDUUUUDUUD"
Returns: 0
32
"DDUDUDDUUDUDDUDUD"
Returns: 8007
14
"UDUUU"
Returns: 119
28
"UDDUUDDDUUDDDDDDUUDUU"
Returns: 0
34
"UUUUUUUUUUU"
Returns: 100947
42
"UUUUUUUUUUUUUUUU"
Returns: 65780
21
"DDDD"
Returns: 0
20
"U"
Returns: 16796
48
"UDDDDDDDDDDDDUDDDDUDUUU"
Returns: 14950
3
"D"
Returns: 0
20
"D"
Returns: 16796
34
"DDDUDDDDDDDDDDDUU"
Returns: 18
30
"U"
Returns: 9694845
4
"U"
Returns: 2
32
"UDDDDUUDUUD"
Returns: 319298
14
"UDDDDUD"
Returns: 28
12
"DDUUU"
Returns: 8
26
"DDDDDDDDDDDDDDUDDDDD"
Returns: 0
42
"UUUUUUUUUUUU"
Returns: 14307150
30
"UUUDUUUUUU"
Returns: 54263
42
"UUUUUU"
Returns: 417819120
18
"DUUD"
Returns: 3347
46
"DDDUDDDDDDDDDDDDD"
Returns: 2035800
18
"DDDDDDDD"
Returns: 10
8
"DUU"
Returns: 6
48
"DDUUDDDDDDDDDDDDDD"
Returns: 7888725
15
"DUUDDDD"
Returns: 0
40
"DDDDU"
Returns: 409169930
2
"U"
Returns: 1
43
"DUUUUDUUUDDUDUUUUDUD"
Returns: 0
4
"UU"
Returns: 1
4
"D"
Returns: 2
4
"U"
Returns: 2
38
"DDUDUUDUDU"
Returns: 51586010
50
"DDUDDDDDDDDD"
Returns: 84324081
42
"DDDUUDDDDDUDDUDDUDDD"
Returns: 100947
36
"UUUUUUUUUDUUDU"
Returns: 100947
28
"DUUDDDUDDDUDD"
Returns: 4368
28
"DUDDDUDDDUDDDD"
Returns: 455
48
"UUU"
Returns: 711407953
12
"UUU"
Returns: 81
18
"UUU"
Returns: 4027
26
"UDU"
Returns: 727389
20
"DD"
Returns: 16795
40
"DDUDDDDDDDUUDDDDDDDDDDUDDDDDDD"
Returns: 0
12
"D"
Returns: 132
32
"DDUD"
Returns: 32676651
6
"U"
Returns: 5
12
"DD"
Returns: 131
20
"UDDDUDUDUD"
Returns: 330
20
"UDUUDUUU"
Returns: 715
26
"DUUDDUUUUU"
Returns: 6188
38
"UUUDUUU"
Returns: 322543285
8
"U"
Returns: 14
8
"DDDD"
Returns: 1
40
"DUUDDUDDUUUDDDDDDUUDDUUDUUDDDDDUD"
Returns: 1
25
"DDDUUDDDDDDU"
Returns: 0
38
"DDDUDUDDDDDDDDDUD"
Returns: 26334
36
"DDDDDDDDDDUDDDDDDDDD"
Returns: 0
8
"DU"
Returns: 13
36
"UDUUDDUDDDDDDD"
Returns: 490314
38
"DUDDDUUDDUDUUDDDD"
Returns: 319770
14
"DDDUDDDDDDDDDD"
Returns: 0
46
"UUUUUUU"
Returns: 388724757
24
"DUDUUDD"
Returns: 41036
32
"UD"
Returns: 35357670
26
"DDDDDDDDDDDD"
Returns: 14
50
"UD"
Returns: 946357703
5
"U"
Returns: 0
2
"D"
Returns: 1
10
"DD"
Returns: 41
28
"U"
Returns: 2674440
48
"UDDUDDDDUUDUDDDUUUDUDUUDDUDDUUUDDDUD"
Returns: 286
38
"DDDDDUUUUUDDUUUD"
Returns: 100947
22
"UUUUU"
Returns: 12310
38
"UDDUUD"
Returns: 797662006
20
"UDDDDDDD"
Returns: 286
50
"UDUUUUUUUUD"
Returns: 820800668
44
"DUUU"
Returns: 309319711
15
"DDDUDDD"
Returns: 0
13
"D"
Returns: 0
36
"DUDDUDUUDDDUDDDDUDUDDUUDDDDDDDD"
Returns: 0
30
"U"
Returns: 9694845
2
"D"
Returns: 1
14
"UUUD"
Returns: 302
44
"DDDDDDDUDDDDDUDUDUDDDDDDUUDDDUDUDDDDUUU"
Returns: 0
22
"DDU"
Returns: 57762
44
"DUDUDUUUUUDDDDDDDUDUDDDDDD"
Returns: 11628
10
"U"
Returns: 42
24
"DDDUUDDD"
Returns: 12087
38
"DDUDUDDUDDUUDDDDDDUUDDDDUD"
Returns: 13
28
"UUUU"
Returns: 1693576
16
"DDDDDU"
Returns: 55
35
"UUUUUUUUUDUUUUU"
Returns: 0
14
"DDD"
Returns: 302
44
"UUUUDUUUUUDUUU"
Returns: 44299015
17
"DDDDDDDD"
Returns: 0
50
"DDDDDDDDUDDDDDDDDDD"
Returns: 3365856
4
"UU"
Returns: 1
16
"DDUDUUDUDDUDUDD"
Returns: 0
50
"DDUUUDUDUDUDUDUD"
Returns: 247555533
50
"UUUUDDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDUDDDDUDUD"
Returns: 1
48
"UUDUUDDDU"
Returns: 549009398
6
"D"
Returns: 5
48
"U"
Returns: 904135723
44
"UUDUUDUDU"
Returns: 168754967
50
"UUDDDDUUDUUUU"
Returns: 460334997
2
"UD"
Returns: 1