atcoder#ARC124F. [ARC124F] Chance Meeting
[ARC124F] Chance Meeting
Score : points
Problem Statement
Given is a grid with rows and columns. Let denote the square at the -th row from the top and -th column from the left.
Initially, a camel is on , and a cat is on .
You can send the following four kinds of orders.
R
: Move the camel on to .D
: Move the camel on to .r
: Move the cat on to .u
: Move the cat on to .
A sequence of orders satisfying all of the four conditions below is said to be good. Find the number of good sequences of orders, modulo .
- The final position of the camel will be .
- The final position of the cat will be .
- The following will happen exactly once: the camel and the cat are on the same square after an order is processed.
- Neither the camel nor the cat will leave the grid.
Constraints
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
Output
Print the number of good sequences of orders, modulo .
2 2
16
- The good sequences of orders include
DRur
,DurR
,RruD
,RDru
, but notDRru
,RRR
.
200000 200000
412709667
- Be sure to print the count modulo .