We are given a square bitmap of size $2^m \times 2^m$. Each pixel of the bitmap is either white or black. Such a bitmap can be represented in a compressed form using a quadtree. If all pixels of the bitmap are white, the tree consists of a single node with the label 0. If all pixels are black, the tree has a single node with the label 1. Otherwise, the root of the tree has the label 4 and possesses four subtrees, which correspond to the four quadrants of the bitmap of size $2^{m-1} \times 2^{m-1}$ (in the order: top-left, top-right, bottom-left, and bottom-right). The tree can be described by a word composed of the characters 0, 1, and 4: the description of the tree begins with the label of its root, followed by the descriptions of its subtrees in order. The figure below shows an example bitmap for $m = 3$ and its corresponding quadtree, described by the word 404004111014001410011:

An area is defined as a maximal set of adjacent black pixels (where pixels are adjacent if they share a side)*. For a given word describing the bitmap, determine the number of areas and the size of the largest one. In the example above, there are two areas with sizes 24 and 5.

Input

The first line of the input contains a single integer $m$ ($m \ge 0$), representing the size of the bitmap. The second line contains a non-empty word encoding the bitmap, composed of the characters 0, 1, and 4. You may assume that the input is correct; in particular, the height of the quadtree (the number of edges on the path from the root to the deepest node) is no greater than $m$. The bitmap contains at least one black pixel.

Output

Your program should output two lines. The first line should contain the number of areas in the bitmap. The second line should contain the size of the largest area. The second number can be very large, so you should output its remainder modulo $10^9 + 7$.

Examples

Input 1

3
404004111014001410011

Output 1

2
24

Note

*Formally, an area is a set of black pixels such that from any pixel in the set, one can reach any other pixel in the set by passing through a sequence of black pixels where each consecutive pair shares a side. An area is called maximal if it cannot be enlarged by any other black pixel while remaining an area. In this problem, we only consider maximal areas.

Subtasks

The test set is divided into the following subtasks. Tests for each subtask consist of one or more separate test groups. The number $n$ denotes the length of the word describing the bitmap.

If your program correctly outputs only one of the numbers, you will receive 50% of the points assigned to the test. However, it must still output two lines, each containing an integer from 0 to $10^9 + 6$.