Cho các số nguyên dương \(n,m,k\) và một hoán vị \(p\) của \(1,2,\ldots,k\).

Một bức tranh là ma trận \(n\times m\) mà mỗi phần tử là một số nguyên trong \([1,k]\). Ký hiệu \(A_{i,j}\) là phần tử ở hàng \(i\) từ trên xuống và cột \(j\) từ trái sang.

Hai bức tranh \(A,B\) giống hệt nhau, ký hiệu \(A=B\), khi \(A_{i,j}=B_{i,j}\) với mọi \(1\le i\le n\), \(1\le j\le m\).

Hai bức tranh \(A,B\) tương tự nhau, ký hiệu \(A\sim B\), khi có thể biến \(A\) thành \(B\) bằng một số lần thực hiện một trong hai phép biến đổi:

1. Chuyển hàng đầu tiên của \(A\) xuống thành hàng cuối cùng.
2. Chuyển cột đầu tiên của \(A\) sang thành cột cuối cùng.

Có thể chứng minh rằng cả quan hệ giống hệt nhau và quan hệ tương tự nhau đều là quan hệ tương đương.

Với một bức tranh \(A\), định nghĩa bức tranh \(f(A)\) bởi

Bức tranh \(A\) được gọi là đẹp khi và chỉ khi \(f(A)\sim A\).

Bạn cần trả lời hai câu hỏi:

1. Có thể chọn nhiều nhất bao nhiêu bức tranh đẹp đôi một không giống hệt nhau?
2. Có thể chọn nhiều nhất bao nhiêu bức tranh đẹp đôi một không tương tự nhau?

In các kết quả theo modulo \(998\,244\,353\).

Dữ liệu vào

• Dòng đầu chứa ba số nguyên dương \(n,m,k\).
• Dòng thứ hai chứa \(k\) số nguyên \(p_1,p_2,\ldots,p_k\), là một hoán vị của \(1,2,\ldots,k\).

Dữ liệu ra

In hai dòng:

• Dòng đầu là đáp án của câu hỏi 1 theo modulo \(998\,244\,353\).
• Dòng thứ hai là đáp án của câu hỏi 2 theo modulo \(998\,244\,353\).

Bài có hai câu hỏi độc lập về điểm số. Dù chỉ giải một câu hỏi, bạn vẫn phải in đủ hai số theo đúng định dạng.

Ràng buộc

Với mọi \(1\le i\le k\), \(1\le p_i\le k\) và \(p_1,p_2,\ldots,p_k\) là một hoán vị của \(1,2,\ldots,k\).

Chấm điểm

Trong từng phần:

• Trả lời đúng câu hỏi 1 trên mọi dữ liệu nhận được \(70\%\) số điểm của phần.
• Trả lời đúng câu hỏi 2 trên mọi dữ liệu nhận được \(30\%\) số điểm của phần.

Ví dụ

4 4 2
2 1

774
60

8 10 3
1 2 3

412733925
108590870

Nguồn

Kỳ thi tập huấn đội tuyển quốc gia Trung Quốc 2026, CCF, giấy phép CC BY-NC.