Problem X
Hola Íslenskra Fræða

Stjórn Háskóla Íslands er loksins búin að taka ákvörðun varðandi holuna sem ber nú nafnið Hola Íslenskra Fræða. Nú er búið að ákveða að aldrei mun verða af þessari byggingu en samt þarf að gera eitthvað við þessa holu því með þessu áframhaldi verður hún að lokum friðlýst. Lausnin á þessum skemmtilega vanda er að grafa dýpri holu! Þitt verk er nú að aðstoða við skipulagningu holugraftar næstu tvo daga þar til að ráðinn er endanlegur starfsmaður í það verk. Þú hefur til umráða $n$ starfsmenn sem eru að grafa niður $n$ smærri holur í holunni. Einnig hefurðu til umráða nokkrar pumpur til að fjarlægja vatn úr holunum því eins og vanalega rignir flest alla daga í Reykjavík. Þar sem þú mættir ekki fyrr en um hádegi fyrri daginn af þessum tveimur eru menn búnir að raða sig niður á holur. Því þarft þú nú að taka tvær ákvarðanir. Í fyrsta lagi þarftu að velja holur til að raða pumpum á. Þú hefur fleiri en $n$ pumpur til umráða svo þú getur sett pumpur á eins margar holur og þú vilt, en ekki fleiri en eina pumpu á hverja. En gallinn er að pumpurnar eru svo háværar að enginn vill vinna tvo daga í röð hjá pumpu. Þú verður því sjá til þess að þegar þú raðar niður fólki á sömu $n$ holur daginn eftir er enginn aftur hjá pumpu. Þetta er svosem ekki gríðarlega flókið verk, en sumir úti í Tæknigarði fara að fylgjast með þessu. Þau spyrja sig hvað ætli séu margar leiðir sem þú hafðir getað valið pumpur og fólk á holur. Getur þú svarað þessu? Þar sem þetta getur verið mjög stór tala á að gefa svarið modulo $10^9+7$.

Inntak

Eina lína inntaksins inniheldur eina heiltölu $1 \leq n \leq 10^7$, fjölda hola og starfsmanna.

Úttak

Eina lína úttaksins inniheldur fjölda leiða sem þú hefðir getað raðað niður fólki og pumpum, gefið modulo $10^9 + 7$.

3

18

100

725034763