定义对一个无前导 的数字串 的压缩为：
定义一个空串 ；
从前往后顺次找到 的每个极长的连续元素段，设这个极长段是 个 ，那么 ，这里的 是字符串的拼接；
，完成一次压缩。
请注意，一个串只有唯一的压缩结果，222 只能被压缩为 32，而不能是 121212，2212 等任意其它串。
222
32
121212
2212
现在给出一个数字串 ，问有多少种初始的数字串 满足 经过恰好 次压缩后可以得到 。
一行一个数字串 。
一行一个整数，表示可能的初始串的数量对 取模后的值。
22
1
原数字串只能是 22。
对于 的数据，。
