CF477D.Dreamoon and Binary

Dreamoon 看到地上写着一个大整数 $x$，并希望将其以二进制形式打印出来。Dreamoon 已经将 $x$ 转换成了二进制格式。现在，他打算用如下方式打印它。

他有一个整数 $n=0$，并且每次可以无限次地执行如下两种操作（按任意顺序）：

1. 以二进制形式（无前导零）打印 $n$，每次打印会将输出追加到之前所有的打印内容之后。
2. 将 $n$ 增加 $1$。

我们定义“理想序列”为一组能够恰好按照上述规则打印出 $x$ 的二进制表示（无前导零）并且以打印操作（即操作 1）结尾的操作序列。Dreamoon 想知道一共有多少种不同的理想序列，以及最短理想序列的长度是多少。

由于答案可能很大，请将结果对 $1000000007$ ($10^{9}+7$) 取模。

理想序列的字符串表示定义为由字符 '1' 和 '2' 组成的字符串，第 $i$ 个字符对应进行的第 $i$ 个操作。如果两个理想序列字符串表示不同，则视为不同的理想序列。

输入只有一行，一个不含前导零的二进制整数，表示 $x$（$1 \leq x < 2^{5000}$）。

第一行输出不同理想序列的数量，对 $1000000007$ 取模。

第二行输出最短理想序列的长度，对 $1000000007$ 取模。

对于第一个样例，唯一的最短理想序列为「222221」，长度为 $6$。

对于第二个样例，有三种理想序列：「21211」、「212222222221」、「222222222222222222222222221」。其中最短的理想序列长度为 $5$。

由 ChatGPT 5 翻译