[Bjoi2014]路径

时间限制:10s      空间限制:256MB

题目描述

 

在一个N个节点的无向图(没有自环、重边)上,每个点都有一个符号,
可能是数字,也可能是加号、减号、乘号、除号、小括号。你要在这个图上数
一数,有多少种走恰好K个节点的方法,使得路过的符号串起来能够得到一
个算数表达式。路径的起点和终点可以任意选择。
所谓算数表达式,就是由运算符连接起来的一系列数字。括号可以插入在
表达式中以表明运算顺序。
注意,你要处理各种情况,比如数字不能有多余的前导0,减号只有前面
没有运算符或数字的时候才可以当成负号,括号可以任意添加(但不能有空括
号),0可以做除数(我们只考虑文法而不考虑语意),加号不能当正号。
例如,下面的是合法的表达式:
-0/0
((0)+(((2*3+4)+(-5)+7))+(-(2*3)*6))
而下面的不是合法的表达式:
001+0
1+2(2)
3+-3
--1
+1
()


输入格式

第一行三个整数N,M,K,表示点的数量,边的数量和走的节点数。
第二行一个字符串,表示每个点的符号。
接下来M行,每行两个数,表示一条边连的两个点的编号。
1≤N≤20,0≤M≤N×(N-1)/2,0≤K≤30


输出格式

输出一行一个整数,表示走的方法数。这个数可能比较大,你只需要输出
它模1000000007的余数即可。


样例输入

6 10 3
)(1*+0
1 2
1 3
1 4
2 3
3 4
2 5
3 5
3 6
4 6
5 6

样例输出

10
//一共有10条路径,构成的表达式依次是101, (1), 1+1, 1+0, 1*1, 1*0, 0+0,
0+1, 0*0, 0*1

提示

没有写明提示


题目来源

鸣谢佚名上传