Dreamoon 看到地上写着一个大整数 x,想要将其二进制形式打印出来。 Dreamoon 已经完成了将 x 转换为其二进制格式的部分。现在他将按照以下方式打印它。
他有一个整数n = 0,并且只能以任意顺序执行以下两个操作,每次操作次数不限:
1. 以二进制形式打印 n,不带前导零,每次打印都会附加到前一次打印的右侧。
2. 将 n 加 1。
让我们将理想序列定义为可以成功打印 x 的二进制表示形式且不带前导零并以打印操作(即操作 1)结束的操作序列。 Dreamoon 想知道有多少种不同的理想序列以及最短理想序列的长度(在操作中)。
答案可能很大,因此请以 1000000007 (109 + 7) 为模打印它们。
让我们将理想序列的字符串表示形式定义为由“1”和“2”组成的字符串,其中字符串中的第 i 个字符与执行的第 i 个操作相匹配。如果两个理想序列的字符串表示不同,则它们被称为不同的序列。
输入
输入的单行包含一个表示 x (1 ≤ x < 25000) 的二进制整数,不带前导零。
输出
输出的第一行应包含一个整数,表示以 1000000007 (109 + 7) 为模的不同理想序列的数量。
输出的第二行包含一个整数,表示理想序列模 1000000007 (109 + 7) 的最小长度。
示例
输入 #1
101
输出 #1
1 6
输入 #2
11010
输出 #2
3 5
注意
对于第一个样本,最短且唯一理想的序列是长度为 6 的《222221》。
对于第二个样本,存在三个理想序列“21211”、“212222222221”、“222222222222222222222222221”。其中最短的长度为5。