时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
题目描述
“子串是什么呢？”泽渡真琴问道。
“子串……就是子的串吧？”相沢祐一不解。
“啊呜，那就是 Son String 啦！”泽渡真琴笑了笑。
“子串……就是子的串吧？”相沢祐一不解。
“啊呜，那就是 Son String 啦！”泽渡真琴笑了笑。
小 L 有一个由 
到 
的数字组成的字符串 
，其长度为 
。你希望把这个字符串划分成若干个非空子串。
若划分出了 
个子串，设第 
个子串中奇数的个数为 
，则你希望对于任意 
，满足 
。
你需要求出来合法的划分的方案数。
由于你很喜欢 
，所以你只需要输出这个方案数对 取模的值。
输入描述:
一个由
输出描述:
合法的划分方案数对
备注:
记的数据，有
。