Snowboard
Time limit1sMemory limit1024 MB
Count paths from the top row to the bottom row of an N by M grid, moving down or diagonally down, that pass through exactly P cells, modulo 262.
- Level
Medium6 of 10
- Topics
- Dynamic programming, Combinatorics, Math, Implementation
- Solved
- No attempts yet
Problem
Ongo-Bongo is a snowboarder. On his slope, N rows are laid out, each with M flags, as shown in the picture. Ongo-Bongo wants to pass exactly P flags, starting at the top of the slope and finishing at the bottom. He may slide only downward, moving either to the flag directly below in the same row or to one of the two nearest flags in the row directly below. In how many ways can he do this?
Input
The first line of standard input contains N, M, and P. (0 < N ≤ M ≤ 200, 0 < P < N + M)
Output
On a single line of standard output, print the number of ways modulo 262 (that is, the remainder when divided by 262).
Hint
The picture shows one of twelve ways to descend past 5 flags. In addition, for the slope shown there are 3 more ways to descend past 4 flags and 10 ways to descend past 6 flags.