Будівлі

Будучи комівояжером у глобалізованому світі, Алан завжди багато подорожував. Він ніколи не жив в одному місті кілька років, оскільки його серце завжди прагнуло нових вражень. Однак це нове місто стало його улюбленим — воно таке яскраве. Нещодавно Алан переїхав у Колорвіль, невелике містечко, розташоване між мальовничими горами. Тут Алан нарешті вирішив оселитися і побудувати собі дім — красивий великий дім, який він міг би назвати своїм.

У Колорвілі багато людей мають власні будинки, кожен з яких пофарбований у унікальну комбінацію кольорів, щоб жоден будинок не виглядав так само. Кожна стіна будинку складається рівно з $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$.

Приклади