Problem C
Forðast hlutrunu

Þú færð mynstursstreng $S$. Finndu fjölda stafaruna af lengd $n$ sem samanstanda af enskum hástöfum þannig að $S$ komi ekki fyrir sem hlutruna í stafarununni.

Inntak

Fyrsta lína inntaksins inniheldur streng af enskum hástöfum af lengd að minnsta kosti $1$ og mesta lagi $100$. Þetta er mynstursstrengurinn $S$. Önnur og síðasta lína inntaksins inniheldur jákvæða heiltölu $n$ sem uppfyllir $1 \leq n \leq 10^{18}$, lengd stafarunanna sem á að telja.

Úttak

Prentið fjölda stafaruna af lengd $n$ sem samanstanda af enskum hástöfum og innihalda ekki $S$ sem hlutrunu. Þar sem þessi fjöldi gæti verið afar stór, prentið svarið mátað við $10^9 + 7$.

ABBA
4

456975

X
20

697814725