For her excellent performance, pianist Chevonne was awarded a pearl necklace. The necklace consisted of pearls which form a circle and are numbered clockwise.
To prevent the pearls from being covered with dust, she wants to move pearls from the necklace and wipe them. However, the way to remove the pearls is complex because of their uniqueness of them.
Specifically, every pearl on the necklace has a continuity value . Each turn, Chevonne can choose a pearl with and move the pearl and clockwise consecutive pearls ( pearls in all). Be careful! If the number of remaining pearls is less than , she will be unable to choose pearl . After that, the remaining pearls will form a new circle.
Chevonne will repeat the process till she can't remove any pearls or all the pearls have been removed. She is curious about the maximum number of pearls she could remove and the number of such solutions.
Here, we use a set to describe a solution. The set contains the number if Chevonne chose pearl in some step. Two solutions are different if and only if the sets are different.

The first line of input contains one positive integer .
The following one line contains  non-negative integers separated by spaces. The -th number represents . Pearls are numbered clockwise from  to .

Please output two integers separated by one space.
The first one is the maximum number of pearls Chevonne could remove and the second one is the number of such solutions. Since the number of solutions may be very large, please output it modular .

6
0 1 1 3 3 1

6 3

In the example, all the pearls could be removed by Chevonne, the  possible solutions are shown as follows:
1. Remove the -th pearl in order.
2. Remove the -th pearl in order.
3. Remove the -th pearl in order.