Известно, что сложение и умножение являются ассоциативными операциями. Это значит, что значение выражений вида \(a_1+a_2+\ldots +a_n\) и \(a_1\cdot a_2 \cdot \ldots \cdot a_n\) не зависит от порядка выполнения в них действий и следовательно не меняется при произвольной расстановке в этих выражениях скобок.
В отличии от сложения и умножения, деление — операция не ассоциативная. Так, значение выражения вида \(a_1/a_2/\cdots /a_n\) может меняться при расстановке в нем скобок.
Рассмотрим выражение вида \[p_1 / p_2 / \cdots / p_n,\] где все \(p_i\) — простые числа (не обязательно различные). Найдите количество возможных значений, которые может принять указанное выражение после расстановки в нем скобок, а также количество целых чисел среди этих значений.
Например, выражение \(3/2/2\) после расстановки скобок может принять два значения: \(3/4 = (3 / 2) / 2\) и \(3 = 3 / (2 / 2)\).
Формат входных данных
Первая строка содержит число \(n\) (\(1 \le n \le 200\)). Следующая строка содержат \(n\) натуральных чисел — \(p_1, p_2, \dots, p_n\). Все числа \(p_i\) простые и не превосходят \(10^4\).
Формат выходных данных
На первой строке выведите количество возможных значений, которые может принять выражение \(p_1 / p_2 / \cdots / p_n\) при заданных \(p_i\) после расстановки в нем скобок. На второй строке выведите количество целых чисел среди этих значений.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 2 2
|
2
1
|