Здания

Будучи коммивояжером в глобализированном мире, Алан всегда много путешествовал. Он никогда не жил в одном и том же городе несколько лет, так как его сердце всегда хотело чего-то другого. Однако этот новый город его самый любимый — он такой яркий. Алан недавно переехал в Колорвилль, небольшой городок между прекрасными горами. Здесь, Алан, наконец, решился устроиться и построить себе дом — красивый большой дом, который он мог бы назвать своим собственным.

В Колорвилле у многих людей свои дома — каждый покрашен в отличную от других комбинацию цветов, чтобы ни один дом не выглядел таким же образом. Каждая стена дома состоит ровно из $n\times n$ квадратов, каждый из которых покрашен в определенный цвет (окна и двери также считаются уникальными "цветами"). Стены домов расположены в форме правильного $m$-угольника, с крышей сверху. Согласно глубоким традициям Колорвилля, крыши должны демонстрировать единство среди жителей Колорвилля, поэтому все крыши в Колорвилле имеют один и тот же цвет.

Конечно же, Алан хочет следовать этому обычаю, чтобы убедиться, что он подходит. Однако существует так много возможных дизайнов, из которых можно выбрать. Можете ли Вы сказать Алану, а сколько имеется возможных дизайнов домов? Два дизайна дома считаются одинаковыми, если их можно преобразовать друг в друга простым поворотом.

Входные данные

В одной строке расположены три целых числа $n,m$ и $c$, где

• $n(1\le n\le 500)$ — длина стороны каждой стены, то есть каждая стена состоит из $n\times n$ квадратов;

• $m(3\le m\le 500)$ — количество углов правильного многоугольника;

• $c(1\le c\le 500)$ — количество различных цветов.

Выходные данные

Выведите количество возможных различных дизайнов домов. Поскольку ответ может быть очень большим, выведите его по модулю $10^9+7$.

Примеры