斐波那契单词序列定义如下：$Fib_{0} = b$，$Fib_{1} = a$，$Fib_{n} = Fib_{n-1}Fib_{n-2}$，其中 $n \ge 2$。$Fib_{n}$ 是 $Fib_{n-1}$ 和 $Fib_{n-2}$ 的拼接。

前几个斐波那契单词为：b，a，ab，aba，abaab，abaababa，abaababaabaab，...

如果一个单词 $v$ 可以写成 $v = xuy$（其中 $x$ 和 $y$ 为任意单词，可以为空），则称单词 $u$ 是单词 $v$ 的子串。

编写一个程序：

• 读取一个单词 $\alpha$（由字母 a 和 b 组成的序列）以及斐波那契单词 $Fib_m$ 的序号 $m$；
• 计算单词 $\alpha$ 在 $Fib_m$ 中作为子串出现的次数，以及在 $Fib_m$ 中作为子串出现频率不低于 $\alpha$ 的非空单词的数量；
• 将结果输出到标准输出。

输入格式

第一行包含一个整数 $m$ ($0 \le m \le 1\,000\,000\,000$)。我们将考察斐波那契单词 $Fib_{m}$。第二行包含一个单词 $\alpha$（长度不超过 $1\,000\,000$，且至少包含一个字母 a 或 b）。

输出格式

在唯一的一行中，输出两个由空格分隔的数字。第一个数字是单词 $\alpha$ 在 $Fib_{m}$ 中作为子串出现的次数。第二个数字是在 $Fib_m$ 中作为子串出现频率不低于 $\alpha$ 在 $Fib_{m}$ 中出现频率的非空单词的数量。

两个数字均需对 20062006 取模（即输出这两个数除以 20062006 的余数）。

你可以假设单词 $\alpha$ 是给定斐波那契单词的子串。

样例

输入 1

5
aba

输出 1

3 5

说明

在 $Fib_{5}$ 中，出现频率不低于 aba 的子串有：a，b，ab，ba 和 aba。