Vasya owns three big integers — a,l,r. Let's define a partition of x such a sequence of strings s1,s2,…,sk that s1+s2+⋯+sk=x, where + is a concatanation of strings. si is the i-th element of the partition. For example, number 12345 has the following partitions: ["1", "2", "3", "4", "5"], ["123", "4", "5"], ["1", "2345"], ["12345"] and lots of others.
Let's call some partition of a beautiful if each of its elements contains no leading zeros.
Vasya want to know the number of beautiful partitions of number a, which has each of si satisfy the condition l≤si≤r. Note that the comparison is the integer comparison, not the string one.
Help Vasya to count the amount of partitions of number a such that they match all the given requirements. The result can be rather big, so print it modulo 998244353.
The first line contains a single integer a (1≤a≤101000000).
The second line contains a single integer l (0≤l≤101000000).
The third line contains a single integer r (0≤r≤101000000).
It is guaranteed that l≤r.
It is also guaranteed that numbers a,l,r contain no leading zeros.
Print a single integer — the amount of partitions of number a such that they match all the given requirements modulo 998244353.
135
1
15
2
10000
0
9
1
In the first test case, there are two good partitions 13+5 and 1+3+5.
In the second test case, there is one good partition 1+0+0+0+0.
Name |
---|