题号：NC54340
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
题目描述
给出一个长度为n的操作序列。每个位置为“&”,“|”,“^”中的一个。&表示按位与，|表示按位或，^表示按位异或。
定义一个长度为n+1的01数列(即该数列只包含0和1)是合法的，当且仅当将该操作序列插入这个长度为n+1的数列后，运算结果为1。
具体的讲，如果给出的操作序列为“&|^”,将其插入到序列1010中进行运算:1&0|1^0=1。所以1010就是操作序列“&|^”的一个合法序列。
由于答案可能很大，你只需要输出答案对
取模后的结果。
定义一个长度为n+1的01数列(即该数列只包含0和1)是合法的，当且仅当将该操作序列插入这个长度为n+1的数列后，运算结果为1。
具体的讲，如果给出的操作序列为“&|^”,将其插入到序列1010中进行运算:1&0|1^0=1。所以1010就是操作序列“&|^”的一个合法序列。
这里的运算不考虑运算符之间的优先级，即全部为自左向右依次进行运算。
现在你需要统计对于一个给定的操作序列，有多少个合法序列。由于答案可能很大，你只需要输出答案对
输入描述:
第一行一个正整数n,表示给出的操作序列的长度。
第二行一个长度为n的字符串，表示给出的操作序列。
输出描述:
一行一个整数，表示答案对
备注:
对于前的数据，满足
对于另外
对于的数据，满足