Arya has a habit of recording all the expenses in a year. Last year she was busy so she told her son Ryan to do this for her. Ryan used to write all the expenses in a diary. Some months later he realized that he forgot to add any space or comma between the expenses, so now he has only one large number.↵
↵
However, he remembers that every time the new expense was strictly greater than all of the earlier expenses. Also, expenses do not contain any leading zeroes. He needs your help to find out the number of ways in which he can split the number into a set of expenses keeping in mind the above conditions.↵
↵
Print the answer modulo 109+7.↵
↵
Input Format↵
↵
The first line of input contains a single integer n (1<=n<=5000)↵
↵
The second line contains a positive number consisting of n digits from 0 to 9.↵
↵
Output Format↵
↵
Print a single integer – the number of ways modulo 109+7.↵
↵
Sample Testcase #0↵
↵
Testcase Input↵
↵
5↵
32745↵
↵
Testcase Output↵
↵
4↵
Explanation↵
↵
There are 4 possible ways:↵
↵
32745↵
3 27 45↵
3 2745↵
32 745↵
Sample Testcase #1↵
↵
Testcase Input↵
↵
6↵
288399↵
↵
Testcase Output↵
↵
8↵
Explanation↵
↵
In this case, there are 8 possible ways:↵
↵
288399↵
2 88399↵
2 88 399↵
2 8 8399↵
2 8 83 99↵
28 8399↵
28 83 99↵
288 3999↵
↵
please solve this problem, i am stuck in it.
↵
However, he remembers that every time the new expense was strictly greater than all of the earlier expenses. Also, expenses do not contain any leading zeroes. He needs your help to find out the number of ways in which he can split the number into a set of expenses keeping in mind the above conditions.↵
↵
Print the answer modulo 109+7.↵
↵
Input Format↵
↵
The first line of input contains a single integer n (1<=n<=5000)↵
↵
The second line contains a positive number consisting of n digits from 0 to 9.↵
↵
Output Format↵
↵
Print a single integer – the number of ways modulo 109+7.↵
↵
Sample Testcase #0↵
↵
Testcase Input↵
↵
5↵
32745↵
↵
Testcase Output↵
↵
4↵
Explanation↵
↵
There are 4 possible ways:↵
↵
32745↵
3 27 45↵
3 2745↵
32 745↵
Sample Testcase #1↵
↵
Testcase Input↵
↵
6↵
288399↵
↵
Testcase Output↵
↵
8↵
Explanation↵
↵
In this case, there are 8 possible ways:↵
↵
288399↵
2 88399↵
2 88 399↵
2 8 8399↵
2 8 83 99↵
28 8399↵
28 83 99↵
288 3999↵
↵
please solve this problem, i am stuck in it.
