Леді хоче наступного дня виконати ~N~ завдань, пронумерованих від 1 до ~N~. Вона хоче визначити порядок, у якому вони будуть виконуватися, тому вона складе план. Він складатиметься з певної кількості уподобань – упорядкованих пар (~x, y~) (~1 ≤ x, y ≤ N~ та ~x ≠ y~), таких що вона віддасть перевагу виконанню завдання x перед виконанням завдання ~y~. Більш формально, план складається з певної кількості упорядкованих пар (можливо, нуль) – уподобань, причому жодні упорядковані пари не є однаковими або будь-які упорядковані пари вигляду (~x, x~).

Зауважте, що для заданого плану Леді віддасть перевагу виконанню завдання ~u~ перед завданням ~v~, якщо існує послідовність уподобань, що веде від ~u~ до ~v~. Наприклад, якщо у нас є пари уподобань (1, 2), (2, 3), (3, 4) та (2, 5), то деякі уподобання Леді включатимуть виконання завдання 1 перед 2, 3, 4 та 5, але вона не матиме уподобань щодо того, яке з завдання 4 та 5 виконувати першою.

Оскільки не всі уподобання можуть бути задоволені для заданого плану, Леді виконає якомога більше завдань, які задовольняють уподобання. Це означає, що вона зможе визначити порядок виконання цих завдань, у якому не буде порушення уподобань. Якщо для заданого плану Леді може виконати не більше ніж ~t~ завдань, то існує порядок цих завдань ~a_1, a_2, …, a_t~, такий, що немає двох завдань ~a_j~ та ~a_i~ для ~j > i~, для яких Леді віддає перевагу виконанню завдання ~a_j~ перед завданням ~a_i~.

Тепер Леді цікавиться, скільки існує можливих планів, для яких найбільша кількість завдань, яку вона може виконати, задовольняючи її вподобання, дорівнює рівно ~K~.

Допоможіть їй, написавши програму, яка знаходить кількість можливих планів для цього за модулем 12289.

Вхідні дані:

Перший рядок містить два цілих числа ~N~ та ~K~ (~1 ≤ N ≤ 650~, ~1 ≤ K ≤ N~) – кількість завдань та найбільша кількість завдань, які можна виконати відповідно до уподобань плану.

Вихідні дані:

Виведіть одне число – знайдена кількість планів за модулем 12289.

Система оцінювання:

Бали за кожну підзадачу нараховуються за умови проходження усіх тестів підзадачі, залежності від підзадач немає.

Приклад вхідних даних:

2 2

Приклад вихідних даних:

3

Приклад вхідних даних:

3 1

Приклад вихідних даних:

18

Приклад вхідних даних:

4 3

Приклад вихідних даних:

774

Пояснення до першого прикладу:

Якщо представити уподобання у вигляді стрілок, то три можливі плани з максимум двома діями для виконання: