Limak is a little polar bear. In the snow he found a scroll with the ancient prophecy. Limak doesn’t know any ancient languages and thus is unable to understand the prophecy. But he knows digits!
One fragment of the prophecy is a sequence of n digits. The first digit isn’t zero. Limak thinks that it’s a list of some special years. It’s hard to see any commas or spaces, so maybe ancient people didn’t use them. Now Limak wonders what years are listed there.
Limak assumes three things:
Years are listed in the strictly increasing order;
Every year is a positive integer number;
There are no leading zeros.
Limak is going to consider all possible ways to split a sequence into numbers (years), satisfying the conditions above. He will do it without any help. However, he asked you to tell him the number of ways to do so. Since this number may be very large, you are only asked to calculate it modulo 109 + 7.
Input
The first line of the input contains a single integer n (1 ≤ n ≤ 5000) — the number of digits.
The second line contains a string of digits and has length equal to n. It’s guaranteed that the first digit is not ‘0’.
Output
Print the number of ways to correctly split the given sequence modulo 109 + 7.
Examples
inputCopy
6
123434
outputCopy
8
inputCopy
8
20152016
outputCopy
4
Note
In the first sample there are 8 ways to split the sequence:
“123434” = “123434” (maybe the given sequence is just one big number)
“123434” = “1” + “23434”
“123434” = “12” + “3434”
“123434” = “123” + “434”
“123434” = “1” + “23” + “434”
“123434” = “1” + “2” + “3434”
“123434” = “1” + “2” + “3” + “434”
“123434” = “1” + “2” + “3” + “4” + “34”
Note that we don’t count a split “123434” = “12” + “34” + “34” because numbers have to be strictly increasing.
In the second sample there are 4 ways:
“20152016” = “20152016”
“20152016” = “20” + “152016”
“20152016” = “201” + “52016”
“20152016” = “2015” + “2016”
题意：给定一个字符串，划分必须满足严格单调递增，求问划分的方案数；
思路： dp[ i ][ j ] 表示左起点为 i ，长度>= j 的方案数；那么我们怎么比较两个字符串的大小呢？
考虑 LCP ( longest common prefix ) ，定义 Lcp( a,b )为以 a,b 开头的字串的相同前缀字符的长度；
那么转移方程就很好表示了；
详细见代码：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<string>
#include<bitset>
#include<ctime>
typedef long long ll;
using namespace std;
typedef unsigned long long int ull;
#define maxn 300005
#define ms(x) memset(x,0,sizeof(x))
#define Inf 0x7fffffff
#define inf 0x3f3f3f3f
const long long int mod = 1e9 + 7;
#define pi acos(-1.0)
#define pii pair<int,int>
#define eps 1e-5
#define pll pair<ll,ll>
ll quickpow(ll a, ll b) {
ll ans = 1;
a = a % mod;
while (b > 0) {
if (b % 2)ans = ans * a;
b = b / 2;
a = a * a;
}
return ans;
}
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a%b);
}
int lcp[6000][6000];
int n;
int dp[6000][6000];
char s[6000];
int Lcp(int a, int b) {
if (a >= n || b >= n)return 0;
int &ret = lcp[a][b];
if (~ret)return ret;
ret = 0;
if (s[a] == s[b]) {
ret = Lcp(a + 1, b + 1) + 1;
}
return ret;
}
int f(int l, int len) {
if (s[l] == '0')return 0;
if (l + len > n)return 0;
if (l + len == n)return 1;
int &ret = dp[l][len];
if (~ret)return ret;
ret = 0;
ret = f(l, len + 1);
if (l + len < n) {
int a = Lcp(l, l + len);
ret += (a < len&&s[l + a] < s[l + len + a]) ? f(l + len, len) : f(l + len, len + 1);
if (ret >= mod)ret -= mod;
}
return ret;
}
int main()
{
ios::sync_with_stdio(false);
memset(dp, -1, sizeof(dp));
memset(lcp, -1, sizeof(lcp));
cin >> n >> s;
cout << f(0, 1) << endl;
}