Lulu sinh ra vào ngày 23 tháng 7 năm 2003 tại một khu rừng tên là "Rừng Niên" (Nieun Forest), nằm giữa hai ngôi làng "Henesys" và "Kerning City" trên đảo Victoria của Maple World. Vào thời điểm đó, Rừng Niên là một vùng đất hoang sơ, cằn cỗi, nơi sinh sống của những con khỉ Lupin hoang dã hung dữ, vì vậy ngoài một vài nhà thám hiểm đi lang thang để thưởng ngoạn phong cảnh thiên nhiên, hầu như không có ai lui tới. Tuy nhiên, gia đình của Lulu đã nuôi dạy cô bằng tất cả tình yêu thương giữa khung cảnh lãng mạn của Rừng Niên.

Khi Lulu lớn lên và chuẩn bị vào tiểu học, Rừng Niên đã bị phá hủy hoàn toàn, không để lại dấu vết do dự án tái phát triển đảo Victoria. Gia đình Lulu đã tích cực phản đối, nhưng khi Tổng thống của Maple World lúc bấy giờ là Hắc Pháp Sư (Black Mage) phái quân đoàn đến đàn áp bằng vũ lực, họ buộc phải di cư đến Kerning City.

Sự kiện đó đã để lại chấn thương tâm lý cho Lulu, và cô quyết định tạo ra các tác phẩm nghệ thuật bằng cách sử dụng nhiều phong cảnh khác nhau của Maple World để có thể truyền tải vẻ đẹp của Maple World trong quá khứ, ngay cả khi nó bị hủy hoại bởi sự phát triển bừa bãi sau này. Lulu đã đi du lịch đến nhiều vùng khác nhau như lục địa Ossyria, Edelstein, Grandis, Đền Thời Gian, Arcane River, v.v., vẽ tranh phong cảnh của từng vùng cho các nhà thám hiểm, và cuối cùng trở thành một nghệ sĩ ngôi sao thực thụ.

Sắp tới sinh nhật lần thứ hai mươi, Lulu quyết định tổ chức một buổi triển lãm đặc biệt. Tác phẩm điêu khắc mà Lulu tâm đắc nhất trong buổi triển lãm là "Niên Universe", lấy cảm hứng từ địa hình hình chữ ㄴ (Niên) của Rừng Niên ngày xưa. Lulu chuẩn bị $N$ mảnh ghép hình chữ ㄴ với kích thước khác nhau từ 1 đến $N$, và mỗi mảnh ghép chứa đựng một tác phẩm nghệ thuật điêu khắc đại diện cho một ngôi làng của Maple World. Một mảnh ghép có kích thước $i$ được tạo thành từ $2i-1$ hình vuông đơn vị (kích thước 1x1) ghép lại thành hình chữ ㄴ với chiều ngang $i$ và chiều dọc $i$, và nó đại diện cho ngôi làng số $C_i$.

Lulu muốn ghép $N$ mảnh ghép này lại với nhau mà không có khe hở để tạo thành một tác phẩm điêu khắc hình vuông có chiều ngang $N$ và chiều dọc $N$. Mỗi mảnh ghép có thể xoay tự do, và vì việc đặt các mảnh ghép đại diện cho cùng một ngôi làng cạnh nhau sẽ làm giảm tính nghệ thuật, nên các mảnh ghép như vậy không được phép chia sẻ cạnh với nhau.

Hình A.1: Ví dụ về việc tạo hình điêu khắc đúng cách với 4 mảnh ghép

Hình A.2: Ví dụ không đúng cách do các mảnh ghép đại diện cho cùng một ngôi làng nằm cạnh nhau

Sau khi tìm ra tất cả các ứng viên cho tác phẩm điêu khắc có thể tạo ra, Lulu muốn chọn ra tác phẩm trông hài hòa nhất để chế tác thành tác phẩm thực tế. Khi được cung cấp thông tin về các mảnh ghép mà Lulu đã chuẩn bị, hãy tính số lượng các tác phẩm điêu khắc khác nhau có thể tạo ra. Lưu ý rằng hai tác phẩm điêu khắc có thể trở nên giống nhau bằng cách xoay được coi là cùng một tác phẩm.

Dữ liệu vào

Dòng đầu tiên chứa số lượng mảnh ghép $N$ ($2 \le N \le 3\,000$).

Dòng thứ hai chứa $N$ số nguyên cách nhau bởi dấu cách. Số thứ $i$ là số hiệu ngôi làng $C_i$ mà mảnh ghép có kích thước $i$ đại diện ($1 \le C_i \le 3\,000$).

Dữ liệu ra

In ra số lượng các tác phẩm điêu khắc có thể tạo ra, chia lấy dư cho $998\,244\,353$ ($= 119 \times 2^{23} + 1$). $998\,244\,353$ là một số nguyên tố.

Ví dụ

Dữ liệu vào 1

4
1 2 3 1

Dữ liệu ra 1

9