← 返回题目列表

Codeforces · 477/D

D. Dreamoon 和二进制

中文机器翻译题面 查看原题

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。