All for Nine and Nine for All
Everyone's favorite noontime show, Lunchtime Surprise, launched a new game recently. They called it: All for Nine and Nine for All. There would be boxes, each containing a single digit from 0 to 9, lined up and the team of nine contestants would have to decide which boxes to open. After opening the boxes, we can read the resulting number from left to right. If this number is positive and can be divided evenly by 9, then they either win that amount of money (in pesos) or 99999 pesos, whichever is lower. However, if the resulting number has leading zeros (e.g. reading the number from left to right results in 00144), it is considered an invalid number. Hence, the contetants lose in that case.
After a few episodes, they realized that winning was relatively easy. The researchers needed to revise the rules. In their proposed set of rules, contestants must choose a set of consecutive boxes instead of any set of boxes. All the other original rules apply.
Now, the researchers needed some kind of report that shows that there are less ways to win using their proposed rules, as compared to the original. They shall give examples of box arrangements and show how many ways one can win using the original set of rules, and how many ways to win using their proposed rules.
Input Format
The first line contains a single integer, which is .
The second line contains a string of length , consisting of digits 0-9, describing a box arrangement.
Output Format
Output exactly two lines.
The first line should contain an integer indicating the number of ways (modulo ) one can win using the original set of rules.
The second line should contain an integer indicating the number of ways (modulo ) one can win using the proposed set of rules.
Constraints
Sample Input
5
33931
Sample Output
3
2
Explanation
For the original set of rules, there are three ways.
The contestants can open boxes , and . Reading it from left to right, our contestants go home with 333 pesos!
The contestants can open box only. Reading it from left to right, our contestants go home with 9 pesos!
The contestants can open boxes , , and . Reading it from left to right, our contestants go home with 3393 pesos!
For the second method, there are two ways. These two ways are the cases illustrated as #2 and #3 above.
xxxxxxxxxxint main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ return 0;}