Suppose that the root of the tree is not labeled ~1~, but with an arbitrary label ~x~.

For some ~x~, let ~f_i(x)~ be the value of all paths in the set described by the substring of the input starting with the ~i^\text{th}~ character.

The following recursive relations hold:

1. ~f_i(x) = f_{i+1}(x)~; if the ~i^\text{th}~ character is P (we stay in the root of the tree, with value ~x~)
2. ~f_i(x) = f_{i+1}(2x)~; if the ~i^\text{th}~ character is L (we move to the left child, with value ~2x~)
3. ~f_i(x) = f_{i+1}(2x+1)~; if the ~i^\text{th}~ character is R (we move to the right child, with value ~2x+1~)
4. ~f_i(x) = f_{i+1}(x) + f_{i+1}(2x) + f_{i+1}(2x+1)~; if the ~i^\text{th}~ character is *

The base case is the empty substring – ~f_{N+1}(x) = x~.

The recursive formulas are linear, meaning that we only add constants or multiply by them. Because of this every term ~f_i(x)~ can be written in the form ~f_i(x) = A_i x + B_i~.

The above recursive formulas can then be rewritten as:

1. ~f_i(x) = A_{i+1} x + B_{i+1}~
2. ~f_i(x) = A_{i+1} (2x) + B_{i+1} = (2A_{i+1})x + B_{i+1}~
3. ~f_i(x) = A_{i+1} (2x+1) + B_{i+1} = (2A_{i+1})x + (A_{i+1}+B_{i+1})~
4. ~f_i(x) = A_{i+1} x + B_{i+1} + A_{i+1} (2x) + B_{i+1} + A_{i+1} (2x+1) + B_{i+1} = (5A_{i+1})x + (A_{i+1}+3B_{i+1})~

The output is ~f_1(1) = A_1 1 + B_1~.

We can use dynamic programming to calculate the sequences ~A~ and ~B~. Because the terms in the sequences can get large, it is required to implement big integer arithmetic supporting long addition.