A knight attacks squares on the chess-board as is show in figure 1.

Figure 1: A knight on the square S attacks squares x.

There is a chess-board of dimensions 3 * n, with 3 rows and n columns, where 1 <= n <= 100, and there is a set Z of fields on the chess-board. The rows are numbered from the top to the bottom with numbers from 1 to 3, the columns from the left to the right with numbers from 1 to n.

Knights can be put only on the squares from the set Z and no two of them can attack each other.

We assume that in each column at most one field belongs to the set Z. Thus the set Z may be described with a series: k₁, k₂, ... , k_n, where k_i belongs to {0, 1, 2, 3}. If k_i = 0 then no field in the i-th column belongs to the set Z, else k_i is a number of a row of the only field in this column, which belongs to Z.

Task

• reads from the text file NIE.IN the number of columns on the chess-board n and the description of the set Z,
• computes the maximal number of knights M, that may be put on the chess-board according to the given rules, and L - the number of possible arrangements of M knights on this chess-board,
• writes the results into the text file NIE.OUT.

Input

Output

Example

Your program should look for the file NIE.IN in the current directory and produce the output file NIE.OUT in the current directory too. The file containing the source code of your program should have a name NIE.???, whereas you should put three-letter abbreviation of the used programming language name instead of ???. The same program in executable form should be written in file NIE.EXE