Teningasafn

Atli á afskaplega marga teninga, svo marga að þetta er farið að vera of mikið til að halda utan um. Því er þér úthlutað því verki að mæla teningana hans. Verandi svolítill safnari eru allir teningarnir misstórir og Atli á einn tening af hverri heiltölustærð frá einum og upp í $n$. Teningarnir hans eru $k$-víðir og því ef hliðarlengd tenings er $x$ þá er rúmmál þess $x^ k$. Rúmmál teninganna er því $1^ k, 2^ k, \dots $ og alla leið upp í $n^ k$.

Að $n$ og $k$ gefnu, getur þú fundið heildarrúmmál teninganna? Þetta rúmmál gæti verið mjög stórt, svo skila skal svari mátað við $10^9 + 7$.

Inntak

Inntak er ein lína með tveimur heiltölum $n$ ($1 \leq n \leq 10^{18}$) og $k$ ($1 \leq k \leq 10^3$).

Úttak

Skrifið út heildarrúmmálið mátað við $10^9 + 7$.

Stigagjöf

3 3

36

100 1

5050

276919944311283466 692

764638923