显然是 dp。

看到这个题，首先看到 $5000$ 的范围，想到要平方做。

假如说我们的 dp 数组只开一维的话，那么显然不好处理，很难记录上一个数是什么，于是考虑开两维数组，$f_{i,j}$ 表示 $1 \sim i$，最后一个选好的数的长度是 $j$。这样同时也能记录到最后一个数是什么。

显然有 $n^3$ 做法，即枚举 $i,k < i$，此时 $j$ 已经确定，只需要枚举 $l \leq j$，对于 $l = j$ 暴力比对字符串即可。满足上述条件时 $f_{i,j} = \sum f_{k,l}$。

考虑对于 $l \leq j$，可以前缀和优化。对于字符串比对字典序，可以预处理前缀哈希然后二分/倍增做，最后复杂度是 $n^2 \log n$。

有点细节，自己看吧。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int T,n,m;
const int mod=1e9+7;
int a[5010];
int hs[5010],p=131;
int pw[5010],inv[5010];
int qpow(int a,int b){
	int r=1,bs=a;
	while(b){
		if(b&1) r=r*bs%mod;
		bs=bs*bs%mod,b>>=1;
	}
	return r;
}
signed f[5010][5010];
int has(int l,int r){
	return (hs[r]-hs[l-1]+mod)%mod*inv[l-1]%mod;
}
int cmp(int s,int t,int len){
	if(s<=0) return 0;
	int l=1,r=len;
	if(has(s,s+len-1)==has(t,t+len-1)) return 0;
	while(l<r){
		int mid=l+r>>1;
		if(has(s,s+mid-1)==has(t,t+mid-1)) l=mid+1;
		else r=mid;
	}
	return a[s+l-1]<a[t+l-1];
}
signed main(){
//	system("fc my.out ex.out");return 0;
//	freopen("ex.in","r",stdin);
//	freopen("my.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	pw[0]=inv[0]=1;
	for(int i=1;i<=n;i++){
		pw[i]=pw[i-1]*p%mod;
		inv[i]=qpow(pw[i],mod-2);
	}
	for(int i=1;i<=n;i++){
		char c;
		cin>>c;
		a[i]=c-'0';
		hs[i]=(hs[i-1]+a[i]*pw[i-1]%mod)%mod;
	}
	f[0][0]=1;
	for(int i=1;i<=n;i++){
		f[0][i]+=f[0][i-1];
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<i;j++){
			if(a[j+1]==0) continue;
			f[i][i-j]=(f[j][i-j-1]+cmp(j-(i-j)+1,j+1,i-j)*((f[j][i-j]-f[j][i-j-1]+mod)%mod))%mod;
		}
		for(int j=1;j<=n;j++){
			f[i][j]=(f[i][j]+f[i][j-1])%mod;
		}
	}
	cout<<f[n][n];
	return 0;
}