Binalar

Qlobal dünyada səyyah satıcı olan Alan həmişə çox səyahət edirdi. O, heç vaxt eyni şəhərdə bir neçə il yaşamamışdı, çünki onun qəlbi həmişə başqa bir şey istəyirdi. Ancaq bu yeni şəhər onun ən sevimlisidir — o, çox parlaqdır. Alan yaxınlarda Kolorvillə köçdü, gözəl dağlar arasında kiçik bir şəhər. Burada Alan nəhayət məskunlaşmağa və özünə ev tikməyə qərar verdi — gözəl böyük bir ev, onu öz evi adlandıra biləcəyi bir ev.

Kolorvildə bir çox insanın öz evləri var — hər biri digərindən fərqli rəng birləşməsində boyanmışdır ki, heç bir ev eyni görünməsin. Hər evin divarı dəqiq $n\times n$ kvadratlarından ibarətdir, hər biri müəyyən bir rəngdə boyanmışdır (pəncərələr və qapılar da unikal "rənglər" hesab olunur). Evlərin divarları düzgün $m$-bucaqlı formada yerləşdirilmişdir, üstündə dam var. Kolorvilin dərin ənənələrinə görə, damlar Kolorvil sakinləri arasında birliyi nümayiş etdirməlidir, buna görə də Kolorvildə bütün damlar eyni rəngdədir.

Əlbəttə ki, Alan bu adətə əməl etmək istəyir ki, uyğun gəldiyinə əmin olsun. Ancaq seçmək üçün çoxlu mümkün dizaynlar var. Alana deyə bilərsinizmi, neçə mümkün ev dizaynı var? İki ev dizaynı eyni hesab olunur, əgər onları sadə bir döndürmə ilə bir-birinə çevirmək mümkündürsə.

Giriş verilənləri

Bir sətirdə üç tam ədəd $n,m$ və $c$ verilir, burada

• $n(1\le n\le 500)$ — hər divarın tərəfinin uzunluğu, yəni hər divar $n\times n$ kvadratlarından ibarətdir;

• $m(3\le m\le 500)$ — düzgün çoxbucaqlının künclərinin sayı;

• $c(1\le c\le 500)$ — müxtəlif rənglərin sayı.

Çıxış verilənləri

Mümkün müxtəlif ev dizaynlarının sayını çıxarın. Cavab çox böyük ola biləcəyi üçün onu $10^9+7$ modulu ilə çıxarın.

Nümunələr