Company: rubrik_4oct
Difficulty: medium
Storage Pair Matching Problem Description You have 2N storage drives in a data center laid down sequentially in a rack numbered 1 through 2N. For redundancy purposes, certain pairs of drives are compatible for RAID mirroring based on their firmware versions. You are given M such pairs of drives that are compatible for mirroring. All other pairs of drives are incompatible. In one operation, you can pair adjacent drives in the rack if they are compatible for RAID mirroring. When you pair two drives, they are removed from the rack and the remaining drives slide together in the rack to close the gap (if a gap was created). Your task is to find how many different ways you can do this operation N times. Two ways to do the operation N times are considered different when there exists 1 ≤ i ≤ N such that the pair of disks chosen in the i-th operation is different in those two ways. Find the answer, modulo 998244353 Input Format First line: two integers N and M 2*N is the number of disks M