Falfa defines the bit-value of a string

as the time that string "bit" occurs in the string

and defines

the number of

-length-lowercase-letter-string whose bit-value is

.
Falfa gives you an integer

, and she wants to know the value of

.
Note that the answer may be very big, so you should output the answer modulo

.