Відбір на IOI

Сьогодні відбудеться один з відбіркових контестів на IOI. Зал для контесту представлений у вигляді рядка з $n$ комп'ютерів. Кожен комп'ютер пронумерований цілими числами від $1$ до $n$ зліва направо. У контесті братимуть участь $m$ учасників, пронумерованих цілими числами від $1$ до $m$.

Маємо масив $a$ довжини $m$, де a_i\:(1 \le a_i \le n) вказує на комп'ютер, біля якого $i$-й учасник хоче сісти.

Також є масив $b$ довжини $m$, що складається з символів $"L"$ і $"R"$. Символ b_i вказує на сторону, з якої $i$-й учасник заходить у зал. Символ $"L"$ означає, що учасник заходить у зал лівіше $1$-го комп'ютера і рухається зліва направо, а символ $"R"$ означає, що учасник заходить у зал правіше $n$-го комп'ютера і рухається справа наліво.

Учасники заходять у зал по черзі, від $1$ до $m$. Кожен $i$-й учасник заходить зі сторони b_i і прямує до комп'ютера a_i. Якщо цей комп'ютер вже зайнятий, учасник продовжує рух у тому ж напрямку до першого вільного комп'ютера. Після цього він сідає за цей комп'ютер. Якщо жоден комп'ютер не виявиться вільним, учасник засмучується і покидає змагання.

Засмученість $i$-го учасника визначається як відстань між його бажаним комп'ютером (a_i) і комп'ютером, за який він врешті сів. Відстань між комп'ютерами $i$ і $j$ дорівнює |i - j|.

Числа в масиві $a$ можуть повторюватися. Існує n^m \cdot 2^m можливих пар масивів $(a,b)$.

Розглянемо всі пари масивів $(a,b)$, для яких жоден учасник не засмутиться. Для кожної з таких пар обчисліть суму засмученостей усіх учасників. Знайдіть суму цих чисел. Відповідь потрібно подати по модулю 10^9 + 9.