## 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