#P4322. 压缩规则

    ID: 3538 传统题 1000ms 512MiB 尝试: 21 已通过: 8 难度: 8 上传者: 标签>CF2500提高+/省选-自动机 DP计数 DP线性 DP状态维度消除

压缩规则

题目描述

定义对一个无前导 00 的数字串 ss 的压缩为:

  • 定义一个空串 s′s';

  • 从前往后顺次找到 ss 的每个极长的连续元素段,设这个极长段是 xx 个 yy,那么 s′←s′+x+ys'\gets s'+x+y,这里的 ++ 是字符串的拼接;

  • s←s′s\gets s',完成一次压缩。

请注意,一个串只有唯一的压缩结果,222 只能被压缩为 32,而不能是 121212,2212 等任意其它串。

现在给出一个数字串 tt,问有多少种初始的数字串 ss 满足 ss 经过恰好 22 次压缩后可以得到 tt。

输入格式

一行一个数字串 tt。

输出格式

一行一个整数,表示可能的初始串的数量对 109+910^9+9 取模后的值。

22
1

样例解释

原数字串只能是 22。

数据规模与约定

对于 100%100\% 的数据,1≤∣t∣≤5001\leq |t|\leq 500。