#14. 进化

题目背景

（太长不看）

三个猎人走上岸之后，海嗣们对大主教的失败进行了深刻反思。他们决定寻找一种方式来判断个体之间的进化水平差异。

听说陆地上的人都在警惕海嗣打各种牌，首言者决定去一探究竟，他伪装成伊比利亚的镇民上岸去。

他向大路上的一位绿发菲林提问：“女士，请问，如何，打牌？”

那女子瞥了他一眼，“你和你的问题让我感到可笑，这片大地因狭隘而普及，在我几万年的生命历涯中，纸张赋予了无数生命以智慧。而如今，一名阿戈尔的赌徒或是黎博利的酒鬼，也许连这种以其为载体的，浅薄的娱乐都不知晓。”

“但仍有些许个体的身上，他们留有那个黄金时代所缺乏的谦恭美德……”

首言者失败了。他怎么也想不到，一个活了几万年的生物竟然既认不出一只海嗣，也不会打牌。于是海嗣们仍旧漫无目的地进化着，这片海洋什么也没有改变。

题目描述

对于一次进化，我们采用下面的方式来衡量其价值：

对于1 位二进制变量定义两种运算：

对于 '+'运算，有以下定义：

0+0=0
0+1=1
1+0=1
1+1=1

对于 '*'运算，有以下定义：

0*0=0
0*1=0
1*0=0
1*1=1

运算的优先级是：

1.先计算括号内的内容，再计算括号外的内容。

2.'× '运算优先于'+'运算。

现给定一个未完成的表达式，例如_ + ( _ * _ )，请你在横线处填入数字0或者1 ，请问有多少种填法可以使得表达式的值为0，方案数即为所求。

输入共两行。

第一行为一个数字n，代表给定的表达式中除去数字外的运算符和括号的个数。

第二行为一个包含L个字符的字符串，其中仅包含'(',')','+','*'。

输出共一行，包含一个整数，表示所有的进化方案数。

请注意，由于结果可能很大，请将结果对19260817取模。

样例1

输入：

2
+*

输出：

3

样例2

输入：

4
(+)*

输出：

5

对于的数据，有，且表达式中不含括号。

对于的数据，有。

对于的数据，有。

本题使用文件输入输出

输入文件为evolve.in，输出文件为evolve.out

2022.5.5 update:删除了部分数据中意义不明的括号

Author:Soplit