Ta thực hiện Q hành động . Trong hành động thứ i :

      -  Chọn mảng mà có ít nhất 2 phần tử 

      -   Chia thành 2 mảng không bị rỗng ( tiền tố và hậu tố)

      -   Viết 2 số nguyên L_i và R_i sao cho L_i là phần tử lớn nhất ở bên trái sau khi chia và R_i là phần tử lớn nhất bên phải

      -   Xóa mảng đã chọn khỏi nhóm mảng có thể sử dụng và thêm vào phần nhóm kết quả 

Giả sử mảng ban đầu là [6,3,4,1,2,5] và chúng ta thực hiện các thao tác :

     1. Chọn mảng [6,3,4,1,2,5]  và tách ra [6,3] và [4,1,2,5] . Sau đó ghi L₁ = 6 và R₁ =5 và ta có mảng [6,3] và [4,1,2,5] 

     2. Chọn mảng [4,1,2,5]  và tách ra [4,1,2] và [5] . Sau đó ghi L₂ = 4 và R₂ = 5 và ta có mảng [6,3] , [4,1,2] ,[5]

     3. Chọn mảng [4,1,2]  và tách ra [4] và [1,2] . Sau đó ghi L₃ =4 và R₃ = 2 và ta có mảng [6,3] , [4] , [1,2] , [5] 

 

Ta có 2 con số nguyên N và Q và 2 chuỗi gồm [L₁,L₂,..,L_Q] và [R₁,R₂,...,R_Q] . Hoán vị với kích thước N được coi là hợp lệ nếu ta có thể biểu diễn Q hành động và các hành động đã cho với chuỗi [L₁,L₂,...L_Q] và [R₁,R₂,...,R_Q] 

Tính số hoán vị hợp lệ 

   - Dòng đầu gồm hai số nguyên N và Q ( 1 <= Q< N <= 3.10⁵)

   - Dòng thứ hai gồm Q số nguyên L₁ , L₂ , ... , L_Q (1 <= L_i <= N)

   - Dòng thứ ba gồm Q số nguyên R₁ , R₂ , ... ,R_Q (1 <= R_i <= N)

   - Phải tồn tại ít nhất 1 hoán vị để tạo ra các chuỗi đã cho [L₁,L₂,...,L_Q] và [R₁,R₂,...R_Q]

   Output

    - Một số nguyên duy nhất - số hoán vị hợp lệ , lấy modulo 998244353