Count Substrings

You are given a string $S_0$ of length $N$ consisting of lowercase english alphabets. We define the string $S_i = S_{(i-1)} +$ `reverse`$(S_{(i-1)})$, where `reverse`$(X)$ denotes the string obtained after reversing the string $X$. Given an integer $K$, find the number of times $S_0$ appears as a **substring** in $S_K$. Since the answer can be huge, print it modulo $10^9 + 7$. ### Input - Th