时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
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
.
Falfa gives you an integer
Note that the answer may be very big, so you should output the answer modulo
输入描述:
The first line contains a single integer).
输出描述:
Outputintegers in a single line, separated by space.