Лампочки

У Джона є $n$ лампочок і розподільчий щиток з $n$ перемикачами. Кожна лампочка може бути увімкнена або вимкнена, і натискання $i$-го перемикача змінює стан лампи $i$ з увімкненого на вимкнений і навпаки. Він використовує їх, щоб зіграти у винайдену ним гру. На кожному ході Джон обирає (можливо, порожній) набір перемикачів і натискає їх, таким чином інвертуючи стани відповідних лампочок. Рівно після $m$ ходів Джон хотів би увімкнути перші $v$ лампочок, а решту вимкнути, в іншому випадку він програє. Є лише одне обмеження: йому не можна натискати один і той самий набір перемикачів двічі.

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

Наприклад, якщо $n=4,m=3$ і $v=2$, одна можлива виграшна гра досягається натисканням перемикачів $1,2$ і $4$ на першому кроці, $1$ і $3$ на другому кроці, і $1,3$ і $4$ на останньому. Це вважається еквівалентним, наприклад, спочатку натисканню $1$ і $3$, потім $1,2,4$ і нарешті $1,3,4$.

Вхідні дані

Містить не більше $500$ рядків, по одному на кожен тест. У кожному рядку записані три цілі числа $n(1\le n\le 1000),m(1\le m\le 1000)$ і $v(0\le v\le n)$. Останній рядок містить $000$ і не обробляється.

Вихідні дані

Для кожного тесту виведіть в окремому рядку кількість способів, якими Джон може зіграти в гру, за модулем простого числа $10567201$.

Приклади