题目思路

考虑dp，设f[i][c]表示前i个字符组成的以c为结尾的合法子序列个数。

假设当前位为j，由于要去重，前面所有以j结尾的子序列对于当前位来说同样可以构造，所以只需要考虑前一位不是以j结尾的答案，同时注意当前这一位可以单独放一个算子序列，所以加上1。

所以转移方程f[i][j] = sum(f[i]) - f[i - 1][j] + 1，最后统计sum(f[n - 1])即可。

由于dp转移只需要考虑前一位，所以可以优化空间复杂度为O(1)。

题目描述

小美有一个数字串$x$，她将$x$的所有非空子序列都取了出来，将其中满足相邻数位两两不同的子序列都加入了集合$S$ 中。

她想知道集合$S$的大小最终有多大，请你帮她计算一下吧。

(注意:根据数学知识我们知道，集合中的元素具有互异性，即两两不同) (在本题中，子序列可以存在前导0，也就是说如“011”和“00011”是不同的)

输入描述

输入包含一行一个数字串 $x(0 \le x\le10^{1000000})$，表示小美的数字$x$。 ($x$可能含有前导 0)

输出描述

输出包含一行一个整数，表示集合的大小。 (由于结果可能很大，因此你只要输出答案对 1000000007取的结果)

样例

输入

12121

输出

9