D.java

package codeforces.goodbye2015;

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

/**
 * Created by hama_du on 2016/01/06.
 */
public class D {
    private static final int MOD = 1000000007;

    static int n;
    static char[] ln;
    static int[][] dp0;
    static int INF = 114514;

    static int dfs(int l, int r) {
        if (r >= n) {
            return INF;
        }
        if (dp0[l][r] != -1) {
            return dp0[l][r];
        }
        int ret = 0;
        if (ln[l] == ln[r]) {
            ret = dfs(l+1, r+1) + 1;
        }
        dp0[l][r] = ret;
        return ret;
    }

    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);

        n = in.nextInt();
        ln = in.nextToken().toCharArray();
        dp0 = new int[n][n];
        for (int i = 0; i < n ; i++) {
            Arrays.fill(dp0[i], -1);
        }
        for (int i = 0; i < n ; i++) {
            for (int j = i+1 ; j < n; j++) {
                dfs(i, j);
            }
        }

        int[][] dp = new int[n][n+1];
        for (int i = 0; i < n ; i++) {
            dp[0][i+1] = 1;
        }
        for (int head = 1; head < n ; head++) {
            if (ln[head] == '0') {
                continue;
            }
            long[] imos = new long[n+10];
            for (int i = 0; i < n ; i++) {
                imos[i+1] = (imos[i] + dp[i][head]) % MOD;
            }
            for (int tail = head+1 ; tail <= n ; tail++) {
                int len = tail - head;
                int max = head;
                int min = Math.max(0, head-len+1);

                // [head-len+1...head)[head...tail)
                if (min <= max) {
                    dp[head][tail] += (imos[max+1] - imos[min] + MOD) % MOD;
                    dp[head][tail] %= MOD;
                }

                // [head-len...head)[head...tail)
                if (head-len >= 0) {
                    int addr = dp0[head-len][head];
                    if (addr < len && ln[head-len+addr] < ln[head+addr]) {
                        dp[head][tail] += dp[head-len][head];
                        dp[head][tail] %= MOD;
                    }
                }
            }
        }

        long sum = 0;
        for (int i = 0; i < n ; i++) {
            sum += dp[i][n];
        }
        sum %= MOD;
        out.println(sum);
        out.flush();
    }

    // 以下テンプレにつき略
}