One Pair for Each Creature
Time limit2sMemory limit1024 MB
Count the ways to pair n males on the x-axis with n females on the y-axis so that no two connecting segments cross, modulo 998244353.
- Level
Medium6 of 10
- Topics
- Combinatorics, Math
- Solved
- No attempts yet
Statement
Newt wants to tidy up his magical creatures and split them into pairs. He has male creatures and female creatures. Every male creature stands on the x-axis, and every female creature stands on the y-axis. No creature is at the origin. Male creature is at , and female creature is at . He wants to split all creatures into pairs, where each pair has one male and one female. For each pair, draw a segment between its two creatures. No two segments may intersect. Count the valid ways to form the pairs, and output the answer modulo .
Input
The first line contains one integer (). The second line contains integers in increasing order (, ). The third line contains integers in increasing order (, ).
Output
Print one integer, the number of valid ways to form the pairs modulo .