Xét đoạn code sau:

dfs_order = [] # empty list
def DFS(u):
    visited[u] = True
    dfs_order.append(u)
        for vertex v that is directly connected to u:
        # note that the order of v is totally random
        if visited[v] == False:
            DFS(v)
DFS(random(1,n))

Trong đó:

• Mảng dfs_order sẽ lưu lại thứ tự DFS của đồ thị trên.

Cho một hoán vị của dãy số từ ~1~ tới ~n~, đếm xem có bao nhiêu cấu hình đồ thị khác nhau nhận hoán vị này là một thứ tự DFS hợp lệ. Hai cấu hình đồ thị ~G_1~ và ~G_2~ được gọi là khác nhau nếu tồn tại một cạnh trong ~G_1~ mà không có trong ~G_2~ hoặc ngược lại.

Yêu cầu

Bạn hãy in ra số cấu hình đồ thị thỏa thứ tự DFS được cho.

Dữ liệu

Đầu vào

• Dòng đầu gồm số nguyên dương ~n~ (~1 \leq n \leq 5000~).
• Dòng tiếp theo gồm ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ biểu diễn một thứ tự DFS. Dữ liệu đảm bảo (~a_1, ..., a_n~) là một hoán vị của dãy số (~1, 2, ..., n~).

Kết quả

• Gồm một số duy nhất là số đồ thị nhận hoán vị trên là một thứ tự DFS hợp lệ theo modulo ~998\ 244\ 353~.

Ví dụ

Input 1

2
2 1

Output 1

1

Input 2

3 
3 1 2 

Output 2

3

Giải thích

• Trong test ví dụ đầu tiên, chỉ có một đồ thị, đồ thị đầy đủ kích thước nhận ~2, 1~ làm một thứ tự DFS hợp lệ.
• Trong test ví dụ thứ 2, có 3 đồ thị sau nhận ~3, 1, 2~ làm một thứ tự DFS hợp lệ: