Відбір на 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$.

Вхідні дані

В єдиному рядку задано два цілі числа $n,m(1\le m\le n\le 2000)$.

Вихідні дані

Виведіть одне ціле число — необхідну суму по модулю $10^9+9$.

Приклади