Cho ~n~ đoạn có hai đầu mút nguyên ~[L_i, R_i] (0 \leq L_i \leq R_i \leq 10^{9})~. Từ mỗi đoạn lấy ngẫu nhiên ra một số thực ~L_i \leq x_i \leq R_i~.

Gọi ~E~ là giá trị kỳ vọng của ~max(x_i)~. Tính ~E~ modulo ~998244353~.

Input

Dòng đầu tiên chứa số nguyên dương ~n (n \leq 2000)~ là số bộ dữ liệu của test.

Mỗi dòng trong ~n~ dòng tiếp theo chứa hai số nguyên ~L_i~ và ~R_i~.

Output

In ra một số nguyên duy nhất là kết quả của bài toán ~E~ modulo ~998244353~.

Sample Input 1

1
1 2

Sample Output 1

499122178

Sample Input 2

2
1 2
1 2

Sample Output 2

665496237

Notes

Đáp án của Sample Input 1 là 1.5 (modulo ~998244353~).

Xét thuật toán bubble sort (nguồn Wikipedia):

procedure bubbleSort(A : list of sortable items)
    n := length(A)
    repeat
        /* do this at most K times */
        swapped := false
        for i := 1 to n-1 inclusive do                     
            /* if this pair is out of order */
            if A[i-1] > A[i] then
                /* swap them and remember something changed */
                swap(A[i-1], A[i])
                swapped := true
            end if
        end for
    until not swapped
end procedure

Một hoán vị độ dài ~n~ được gọi là hoán vị đẹp nếu dãy con tăng dài nhất (LIS) của hoán vị đó đạt ít nhất ~n-1~.

Đếm số hoán vị có thể trở thành hoán vị đẹp sau ~k~ lần vòng lặp trong của thuật toán bubble sort được thực hiện (theo module đã cho).

Input

Dòng đầu tiên chứa số nguyên dương ~T (T \leq 50)~ là số bộ dữ liệu của test.

Mỗi dòng trong ~T~ dòng tiếp theo chứa ba số nguyên dương ~n, k, mod (n, k \leq 50, mod \leq 10^{9} + 7)~.

Output

In ra ~T~ dòng mỗi dòng gồm một số nguyên duy nhất là kết quả của bộ dữ liệu tương ứng.

Sample Input 1

2
6 3 998244353
8 3 998244353

Sample Output 1

696
22872

Cho một bàn cờ ~n \times n~. Các hàng được đánh số từ ~1~ tới ~n~ từ trên xuống dưới, các cột được đánh số từ ~1~ tới ~n~ từ trái qua phải (Ô ~(1, 1)~ là góc trái trên và ~(n, n)~ là góc phải dưới).

Trên một số ô của bàn cờ có chứa một quân cờ mang màu trắng hoặc đen (số còn lại không chứa gì), quân cờ ở ô ~(i, j)~ có giá trị là ~w_{ij}~.

Nhiệm vụ của bạn là bốc được hết các quân cờ ra khỏi bàn cờ. Tại mỗi bước, bạn có thể chọn một quân cờ trắng ~u~ và một quân cờ đen ~v~ và xóa chúng ra khỏi bàn cờ trong thời gian ~|w_u - w_v|~. Tuy nhiên, một quân cờ ~(x, y)~ chỉ được phép chọn ở thao tác này nếu hiện tại không có quân cờ ~(x_1, y_1)~ nào khác mà ~x_1 \geq x~ và ~y_1 \leq y~.

Ngoài ra, bạn cũng có thể chọn một quân cờ ~u~ bất kỳ trên bàn cờ và đưa nó ra khỏi bàn trong thời gian ~w_u~.

Bạn hãy tính thời gian ngắn nhất có thể để đưa hết cờ ra khỏi bàn.

Input

Dòng đầu chứa một số nguyên dương ~n (1 \leq n \leq 12)~.

~n~ dòng tiếp theo mỗi dòng chứa một xâu gồm ~n~ ký tự ".", "W" hoặc "B" biểu diễn một ô trống, một ô chứa cờ trắng hoặc một ô chứa cờ đen.

~n~ dòng tiếp theo mỗi dòng chứa một dãy ~n~ số nguyên dương. Số nguyên dương thứ ~j~ của dòng thứ ~i~ là giá trị ~w_{ij} (0 \leq w_{ij} \leq 10^{6}).~

Oụtput

In ra một số nguyên duy nhất là thời gian ngắn nhất để chuyể hết các quân cờ ra khỏi bàn.

Sample Input 1

4
WBB.
BWBW
WBWW
BBBW
1 1 1 0
1 1 1 1
1 1 1 1
1 1 1 1

Sample Output 1

3