Facebook Hacker Cup 2012 Round 1 Solutions: Squished Status

Problem:

Some engineers got tired of dealing with all the different ways of encoding status messages, so they decided to invent their own. In their new scheme, an encoded status message consists of a sequence of integers representing the characters in the message, separated by spaces. Each integer is between 1 and M, inclusive. The integers do not have leading zeroes. Unfortunately they decided to compress the encoded status messages by removing all the spaces!
Your task is to figure out how many different encoded status messages a given compressed status message could have originally been. Because this number can be very large, you should return the answer modulo 4207849484 (0xfaceb00c in hex).
For example, if the compressed status message is "12" it might have originally been "1 2", or it might have originally been "12". The compressed status messages are between 1 and 1000 characters long, inclusive. Due to database corruption, a compressed status may contain sequences of digits that could not result from removing the spaces in an encoded status message.
Input
The input begins with a single integer, N, the number of compressed status messages you must analyze. This will be followed by N compressed status messages, each consisting of an integer M, the highest character code for that database, then the compressed status message, which will be a string of digits each in the range '0' to '9', inclusive. All tokens in the input will be separated by some whitespace.
Output
For each of the test cases numbered in order from 1 to N, output "Case #i: " followed by a single integer containing the number of different encoded status messages that could be represented by the corresponding compressed sequence modulo 4207849484. If none are possible, output a 0.
Constraints
5 <= N <= 25
2 <= M <= 255
1 <= length of encoded status <= 1000

To solve the Squished Status problem, I wrote a following function:

Paths(string, depth) - function calculating the number of possible statuses encoded by a string in the given BASE.

1. If length of string is 0 return 1;
2. If cached number is available for the given depth, return the cached value (that was previously calculated by this function for the current depth);
3. If string starts with 0, return 0; 
4. If length of the string is 1: return 1 if value of the single element of the string is less then BASE, otherwise, return 0;
5. Set l=1; res=0;
6. While the integer value of substring(string, 0, l) is less than BASE: res += paths(t.substring(l, t.length()));

As a means of optimization, I also converted the input string into an array of integers on char-by-char basis, but, probably, the solution.

Code of this function in Java:

        private long paths(int a[], int length, int X){

        if (length == 0) return 1;

        if (a[0] == 0) return 0;

        if (length == 1)

        if (a[0] <= base)

          return 1;

        else 

           return 0;

        if (P[X] > -1) return P[X];

       

        long res = 0;

        int l = 1;

        int n = a[0];

       

        while (l<=length && n <= base){

        res += paths(Arrays.copyOfRange(a, l, length), length-l, X+l);

       

        if (l

        l++;        

        }

        P[X] = res % 4207849484L;

        return P[X];

        }