Count all possible attendance records with length n, which will be regarded as rewardable
First of all, java doesn't like deep recursive calls. I tried running the following mini program on my machine and it only went up to 11398 before ending with a stackoverflow:

public static void main(String[] args) throws Exception {
    recurseTest(0);
}

public static void recurseTest(int n){
    System.out.println(n);
    recurseTest(n+1);
}


Notice that this only stores an int each call.

So you're better of calculating everything in a for loop instead.



It would be nice if we could do a single pass over the entire record choosing which letter to add at that step and update our total (+ helper totals). That way we don't even need to consider memoisation.

Let's look at which totals we want to keep track of to calculate the correct result.

First we have the requirement that the entire string can only have at most 1 letter A. So I would keep track of 2 groups of totals. Those that don't have an A yet. And those that do.

Next we must ensure that we can have at most 2 consecutive Ls. So let's keep track of how many L's are in the end at the previous step.

This leads to the following 6 variables.

long noA0;
long noA1;
long noA2;
long a0;
long a1;
long a2;


where noAx means it doesn't contain an A yet and ends with x letters L.

Here's what we would like to write in each step to update to the new values:

noA0 = noA0 + noA1 + noA2; //added P to any of the previous noA's
noA1 = noA0;
noA2 = noA1;
a0 = noA0 + noA1 + noA2 + a0 + a1 + a2; //added A to noA_ or added P to a_
a1 = a0;
a2 = a1;


But that has the problem that we are using updated values already. So we need to store some temp values instead.

tempnoA0 = noA0 + noA1 + noA2; //added P to any of the previous noA's
tempa0 = noA0 + noA1 + noA2 + a0 + a1 + a2; //added A to noA_ or added P to a_    
noA2 = noA1;
noA1 = noA0;
a2 = a1;
a1 = a0;
noA0 = tempnoA0;
a0 = tempa0;


Now all you have to do is run this in a loop and figure out what the actual end result is. But that shouldn't be too hard right?



A last thing to consider is when to do the modulo. It may well be worth doing this at the right times during the loop as well to reduce the risk of overflowing the long (although I didn't actually look if this would be a real problem or not).