Linear Garden

Ramesses II has just returned victorious from battle. To commemorate his victory, he decided to build a majestic garden. The garden will contain a long line of plants that will run all the way from his palace at Luxor to the temple of Karnak. It will consist only of lotus and papyrus plants, since they symbolize Upper and Lower Egypt respectively.

The garden must contain exactly $n$ plants. Additionally, it must be balanced: in any contiguous section of the garden, the numbers of lotus and papyrus plants must not differ by more than $2$.

The garden can be represented as a string of letters 'L' (lotus) and 'P' (papyrus). For example, for n = 5, there are $14$ possible balanced gardens. In alphabetical order, these are: $\text{LLPLP}$, $\text{LLPPL}$, $\text{LPLLP}$, $\text{LPLPL}$, $\text{LPLPP}$, $\text{LPPLL}$, $\text{LPPLP}$, $\text{PLLPL}$, $\text{PLLPP}$, $\text{PLPLL}$, $\text{PLPLP}$, $\text{PLPPL}$, $\text{PPLLP}$ and $\text{PPLPL}$.

The possible balanced gardens of a certain length can be ordered alphabetically and then numbered starting from $1$. For example, for n = 5, garden number $12$ is $\text{PLPPL}$.

Write a program that, given the number of plants $n$ and a string that represents a balanced garden, calculates the number assigned to this garden modulo a given integer $m$. Note that for the solution, the value of $m$ has no relevance other than simplifying computations. It is known that 1 \leq n \leq 1\ 000\ 000, 7 \leq m \leq 10\ 000\ 000.