Migrated from Lutece 2806 又是数位dp

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

在动态规划专题进行完后，相信大家已经学会了如何进行数位dp。因此本题将作为检验你是否学会数位dp的问题。

给你一个只包含数字的字符串 $S$ 和范围 $[l,r]$ ，你现在要求把 $S$ 分割成任意多子串 $S_i$ ，满足分割后的字符串 $\sum{S_i}=S$ ，$S_i$ 不能有前导 0 ， 且每个 $S_i$ 所对应的数值需要在 $[l,r]$ 的范围内。

你只需要输出方案数对 $998244353$ 取模的结果。

Input

输入三行字符串,分别表示 $S,l,r$

Output

输出方案数对 $998244353$ 取模的结果。

Samples

135
1
15

2

Constraints

$1\le | S |,| l |,| r | \le 10^6$

Note

样例分割方法如下： 第一种："13","5" 第二种："1","3","5"

Resources

2022 UESTC ICPC Training for String and Search Algorithm