Con mã (ô S) tấn công các ô vuông (dấu x) trên bàn cờ như hình dưới. Có một bàn cờ kích thước \(4 \cdot n\), với \(4\) hàng và \(n\) cột, trong đó \(1 \le n \le 100\). Gọi \(Z\) là tập các ô trên bàn cờ. Các hàng được đánh số thứ tự từ trên xuống dưới, từ \(1\) đến \(4\), các cột được đánh số thứ tự từ trái qua phải, từ \(1\) đến \(n\). Quân mã chỉ có thể được đặt trên các ô không thuộc \(Z\) và hai quân bất kỳ không được ăn nhau.

Giả định trong mỗi cột có nhiều nhất một ô thuộc \(Z\). Vì vậy, tập \(Z\) có thể được mô tả bằng chuỗi \(k_1, k_2, \dots, k_n\) trong đó \(k_i \in \{0, 1, 2, 3, 4\}\). Nếu \(k_i = 0\) thì cột \(i\) không có ô nào thuộc \(Z\), ngược lại, ô ở hàng \(k_i\), cột \(i\) thuộc \(Z\).

Hãy tính số lượng tối đa của các quân mã \(M\), có thể đặt trên bàn cờ theo quy tắc trên và số lượng \(L\) cách sắp xếp có thể của \(M\) quân mã trên bàn cờ này.

Input

• Dòng đầu tiên là số nguyên dương \(n\) (\(1 \le n \le 100\)).
• Mỗi dòng trong \(n\) dòng sau ghi một số \(0, 1, 2, 3\) hoặc \(4\).

Output

• In ra hai số \(M\) và \(L\).

Example

2
1
0

4 8

Subtasks

• \(50\%\) số test có ràng buộc bổ sung: \(n \le 25\).
• \(50\%\) số test còn lại không có ràng buộc bổ sung.