不难想到一个 dp：设 $f_i$ 表示划分完 $1\sim i$ 的方案数，那么 $f_i \gets f_j, j < i$，这显然是一个 $O(n^3)$ 的做法。

可以发现能转移到 $f_i$ 的是一段连续的区间，但是中间的 $0$ 不能转移到 $f_i$。由于 $f_i$ 可以转移到的状态也是一段连续的区间，可以想到用 $f_i$ 去转移其他的状态。

$f_i \to f_j, j \in [i+|l|, i+|r|]$。

事实上这个区间中只有 $i+|l|$ 和 $i+|r|$ 可能转移不到 $f_i$，那么我们就有了一个优秀的 $O(n^2)$ 的做法：

https://codeforces.com/contest/1051/submission/234047134

那么转移实质上是一个单点查，区间加，直接树状数组维护即可，复杂度的瓶颈变成了检验转移是否合法。

同时检验是一个经典的字符串字典序比较问题，直接用 $hash$ + 二分求最长公共前缀判断下一个位置的大小即可。

时间复杂度 $O(n \log n)$。

然而这题卡自然溢出，WA 了 100 年。

代码很简单：

#include <bits/stdc++.h>
 
using namespace std;
 
typedef unsigned long long ull;
typedef long long ll;
 
inline int read() {
	int x = 0, f = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
	for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
	return x * f;
}
 
const int N = 1000010;
const int mod = 998244353;
const int base = 2009107;
const int hash_mod = 1e9 + 9;
 
char a[N], l[N], r[N];
int n, sl, sr, max_len, f[N], tr[N];
ll hsh[5][N], pw[N];
 
ll get(int l, int r, ll hsh[]) {
	return (hsh[r] - hsh[l - 1] * pw[r - l + 1] % hash_mod + hash_mod) % hash_mod;
}

bool check(int st, int ed) {
	int len = ed - st + 1;
	if (len == sl) {
		int ql = 1, qr = sl, ans = 0;
		while (ql <= qr) {
			int mid = (ql + qr) >> 1;
			if (get(1, mid, hsh[0]) == get(st, st + mid - 1, hsh[2])) ql = mid + 1, ans = mid;
			else qr = mid - 1;
		}
		if (ans != sl && l[ans + 1] > a[st + ans]) return false;
	}
	if (len == sr) {
		int ql = 1, qr = sr, ans = 0;
		while (ql <= qr) {
			int mid = (ql + qr) >> 1;
			if (get(1, mid, hsh[1]) == get(st, st + mid - 1, hsh[2])) ql = mid + 1, ans = mid;
			else qr = mid - 1;
		}
		if (ans != sr && r[ans + 1] < a[st + ans]) return false;
	}
	return true;
}
 
int lowbit(int x) { return x & -x; }
 
int query(int pos) {
	int res = 0; pos ++ ;
	for (; pos; pos -= lowbit(pos)) res = (res + tr[pos]) % mod;
	return res;
}
 
void modify(int pos, int x) { pos ++ ; for (; pos <= n + 1; pos += lowbit(pos)) tr[pos] = (tr[pos] + x) % mod; }
void modifyPoint(int pos, int x) { modify(pos, x), modify(pos + 1, mod - x); }
 
int main() {
	scanf("%s%s%s", a + 1, l + 1, r + 1);
	n = strlen(a + 1), sl = strlen(l + 1), sr = strlen(r + 1), pw[0] = 1;
	max_len = max({n, sl, sr});
	for (int i = 1; i <= max_len; i ++ ) pw[i] = pw[i - 1] * base % hash_mod;
	for (int i = 1; i <= sl; i ++ ) hsh[0][i] = (hsh[0][i - 1] * base % hash_mod + l[i]) % hash_mod;
	for (int i = 1; i <= sr; i ++ ) hsh[1][i] = (hsh[1][i - 1] * base % hash_mod + r[i]) % hash_mod;
	for (int i = 1; i <= n; i ++ ) hsh[2][i] = (hsh[2][i - 1] * base % hash_mod + a[i]) % hash_mod;
	modifyPoint(0, 1);
	for (int i = 0; i <= n; i ++ ) {
		int down = i + sl, up = min(i + sr, n), val = query(i);
		if (down > up) continue;
		if (a[i + 1] == '0') { // 下一段的开头如果是 0 的话，只能转移到 f[i + 1]。
			if (down == i + 1) modifyPoint(down, val * check(i + 1, down));
			continue;
		}
		modifyPoint(down, val * check(i + 1, down));
		if (down + 1 <= up) { // 注意 down == up 时，不能转移。
			modifyPoint(up, val * check(i + 1, up));
			modify(down + 1, val), modify(up, mod - val);
		}
	}
	printf("%d\n", query(n));
	return 0;
}