Ta định nghĩa một cách tách của số \(x\) là một dãy các xâu \(s_1,s_2,\ldots, s_k\) sao cho \(s_1 + s_2 + \ldots + s_k = x\), với phép \(+\) là phép ghép xâu, \(s_i\) là phần tử thứ \(i\) của phép tách này. Ví dụ, số \(12345\) có thể tách như sau: ["1", "2", "3", "4", "5"], ["123", "4", "5"], ["1", "2345"], ["12345"], v.v

Ta gọi một cách tách là chuẩn tắc nếu tất cả các số thành phần sau khi tách đều không có số \(0\) vô nghĩa ở đầu (leading zeros).

Cho ba số nguyên \(a,\ l,\ r\). Tính xem có bao nhiêu cách tách chuẩn tắc số a, sao cho với mỗi số thành phần \(s_i\) luôn thỏa mãn \(l\leq s_i\leq r\).

Lưu ý: phép so sánh thực hiện ở đây là so sánh giữa số nguyên chứ không phải so sánh giữa xâu. Vì kết quả có thể rất lớn, chỉ cần in số dư của nó khi chia cho \(998244353\).

Input

• Dòng đầu tiên chứa số nguyên \(a\) (\(1\leq a\leq 10^{1000000}\));
• Dòng thứ hai chứa số nguyên \(l\) (\(0\leq l\leq 10^{1000000}\));
• Dòng thứ ba chứa số nguyên \(r\) (\(0\leq r\leq 10^{1000000}\));

Dữ liệu đảm bảo rằng \(l\leq r\) và cả \(a, l, r\) đều không có leading zeros.

Output

• In ra một số nguyên là kết quả bài toán.

Examples

Sample input 1

135
1
15

Sample output 1

2

Sample input 2

10000
0
9

Sample output 2

1

Subtasks

• Có \(40\%\) test tương ứng với \(40\%\) số điểm có \(1\leq a\leq 10^{1000}\), \(0\leq l \leq r\leq 10^{1000}\).
• \(60\%\) test còn lại không có ràng buộc gì thêm.