IOI Selection

One of the qualifying contests at the IOI will be held today. The contest hall is a row of $n$ computers. All computers are numbered with integers from $1$ to $n$ from left to right. There will be a total of $m$ participants numbered with integers from $1$ to $m$.

We have an array $a$ of length $m$, where a_i\:(1 \le a_i \le n) is the computer that the $i$-th participant wants to sit at.

We also have another array $b$ of length $m$, consisting of the characters $"L"$ and $"R"$. b_i — this is the side from which the $i$-th participant enters the hall. $"L"$ means that the participant enters the hall to the left of computer $1$, and goes from left to right, and $"R"$ means that the participant enters the hall to the right of computer $n$ and goes from right to left.

Participants in the order from $1$ to $m$ enter the hall one by one. The $i$-th of them enters the hall from the side of b_i and goes to the computer a_i. If this computer is already occupied, they continue in the same direction until the first free computer. After that, they sit down at this computer. If a participant does not meet any free computers, they get upset and leaves the competition.

The frustration of the $i$-th participant is the distance between his desired computer (a_i) and the computer he eventually sat down at. The distance between computers $i$ and $j$ is |i - j|.

The numbers in the array $a$ can be equal. There is n^m \cdot 2^m possible array pairs $(a,b)$.

Consider all pairs of arrays $(a,b)$ such that no participant will be upset. For each of them, we will calculate the sum of the frustrations of all participants. Find the sum of these numbers. The answer must be taken modulo 10^9 + 9.