Uks Is an Apple Fan!!
Time limit2sMemory limit512 MB
Count the number of paths on an N by M grid where each cell directs movement right, down, or both, and every path must end at cell (N, M).
- Level
Medium5 of 10
- Topics
- Dynamic programming, Combinatorics, Matrix
- Solved
- No attempts yet
Problem
Uks is a devoted fan of Gusagwa. Today Uks wants to deliver a gift (
) to Gusagwa. After observing him for several days, Uks has figured out Gusagwa's entire movement pattern.
The place where Gusagwa is can be represented by a rectangular map of size N×M, divided into 1×1 squares. Gusagwa's position can be written as (i, j), where (i, j) means the i-th cell from the top and the j-th cell from the left.
Each cell of the map contains one of the characters E, S, or B, and Gusagwa moves according to this character. When Gusagwa is at (i, j) and the cell contains E, he teleports to (i, j+1); if it contains S, he teleports to (i+1, j); if it contains B, he teleports to either (i, j+1) or (i+1, j). Gusagwa never gets tired, so he keeps moving.
Uks does not know Gusagwa's position, but he knows that no matter where Gusagwa starts moving, his final destination is always (N, M). Uks plans to place the gift at (N, M) so that Gusagwa always takes it. Write a program that computes the number of paths along which Gusagwa takes the gift. Whenever Gusagwa moves onto the cell where the gift is placed, he always takes the gift.
Input
The first line gives the height N and width M of the map. (1 ≤ N, M ≤ 3,000)
From the second line, N lines give the map of the place where Gusagwa is. (N, M) contains X, which marks the destination.
When moving as written on the map, Gusagwa never leaves the map.
Output
On the first line, print the number of paths along which Gusagwa takes the gift. The number of paths can be very large, so print it modulo 1,000,000,009 (10^9 + 9).