NOIP '18 P5 - Grid-filling Game

View as PDF

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

There is an grid. A valid path from the upper left corner to the bottom right corner is a path such that movements are only allowed in the right or in the down directions, and we may use a string to represent the path in the way that if in the -th step we move right then the -th character of is R while if in the -th step we move down then the -th character of is D. The length of shall be .

Now we are going to fill the grids with number 0 or 1. For a valid path , if we write down the numbers in the grids on the path (including the start and the end, in the order we visit the grids), we get a string of length , . Compute the number of ways to fill the grids with 0 or 1, modulo , such that for any two valid paths , if in the lexicographic order, then in the lexicographic order.

Input Specification

The input consists of one line with two integers separated by a space denoting the size of the grid. denotes the number of rows in the grid, while denotes the number of columns in the grid.

Output Specification

The output consists of one line containing an integer denoting the number of valid ways to fill the grid with 0 and 1 subject to the constraint mentioned in the statement, modulo .

Sample Input 1

2 2

Sample Output 1

12

Explanation

The two possible paths from the upper-left corner to the bottom-right corner have and . As a result, the invalid ways to fill the grid with 0 and 1 are exactly the ways to fill the grids such that , which happens if and only if when the upper-right corner is 1 and the bottom-left corner is 0. Therefore, the answer in this case shall be .

Sample Input 2

3 3

Sample Output 2

112

Sample Input 3

5 5

Sample Output 3

7136

Test Case
1-4
5-10
11-13
14-16
17-20