Under construction

Still being built. Things may change

One Pair for Each Creature

Time limit2sMemory limit1024 MB

Summary
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 nn male creatures and nn 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 ii is at (xi,0)(x_i, 0), and female creature ii is at (0,yi)(0, y_i). He wants to split all creatures into nn 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 998 244 353998\,244\,353.

Input

The first line contains one integer nn (1≤n≤100 0001 \le n \le 100\,000). The second line contains nn integers x1,…,xnx_1, \ldots, x_n in increasing order (−109≤x1<⋯<xn≤109-10^9 \le x_1 < \cdots < x_n \le 10^9, xi≠0x_i \neq 0). The third line contains nn integers y1,…,yny_1, \ldots, y_n in increasing order (−109≤y1<⋯<yn≤109-10^9 \le y_1 < \cdots < y_n \le 10^9, yi≠0y_i \neq 0).

Output

Print one integer, the number of valid ways to form the pairs modulo 998 244 353998\,244\,353.

Examples3

  1. Example 1

    Input
    2
    -1 1
    1 2
    
    Expected output
    2
    
  2. Example 2

    Input
    2
    -1 1
    -1 2
    
    Expected output
    2
    
  3. Example 3

    Input
    2
    1 2
    1 2
    
    Expected output
    1