题目描述

定义对一个无前导 $0$ 的数字串 $s$ 的压缩为：

• 定义一个空串 $s'$；

• 从前往后顺次找到 $s$ 的每个极长的连续元素段，设这个极长段是 $x$ 个 $y$，那么 $s'\gets s'+x+y$，这里的 $+$ 是字符串的拼接；

• $s\gets s'$，完成一次压缩。

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

现在给出一个数字串 $t$，问有多少种初始的数字串 $s$ 满足 $s$ 经过恰好 $2$ 次压缩后可以得到 $t$。

输入格式

一行一个数字串 $t$。

输出格式

一行一个整数，表示可能的初始串的数量对 $10^9+9$ 取模后的值。

22

1

样例解释

原数字串只能是 22。

数据规模与约定

对于 $100\%$ 的数据，$1\leq |t|\leq 500$。