Valid Arithmetic Expression Paths

You are given an undirected graph with N nodes (indexed from 1 to N) and M edges. Each node is assigned exactly one symbol which may be a digit (0–9) or one of the characters: +, -, *, /, (, ). Your task is to count the number of simple paths that visit exactly K nodes such that the concatenation of the symbols along the path forms a valid arithmetic expression.

An arithmetic expression is defined as a series of numbers connected by binary operators. Parentheses may be inserted arbitrarily (though they cannot be empty) to denote the evaluation order. Note the following conditions that must be satisfied for an expression to be valid:

• Numbers must not have extra leading zeros (except the number 0 itself).
• A minus sign (-) can only serve as a unary negative operator if it appears at the beginning of the expression or immediately after an operator or an opening parenthesis.
• A plus sign (+) cannot be used as a unary positive operator.
• Parentheses must properly match and cannot be empty (i.e. () is not allowed).
• Division by zero is permitted from the grammar perspective (semantics are not evaluated).

For example, the following are valid expressions:

-0/0
((0)+(((2*3+4)+(-5)+7))+(-(2*3)*6))

While these are invalid:

001+0
1+2(2)
3+-3
--1
+1
()

A simple path in the graph is one that does not visit any node more than once. The path may start and end at any nodes. Count the number of such paths consisting of exactly K nodes whose corresponding symbol string is a valid arithmetic expression as per the above rules.

inputFormat

The input begins with a line containing three integers N, M and K separated by spaces, where N is the number of nodes, M is the number of edges, and K is the number of nodes to be visited in the path.

The second line contains N symbols separated by spaces. Each symbol is either a single digit (0–9) or one of these characters: +, -, *, /, (, ).

Each of the next M lines contains two integers u and v (1-indexed) indicating that there is an undirected edge between nodes u and v. It is guaranteed that there are no self-loops and no multiple edges.

outputFormat

Output a single integer representing the number of valid simple paths that contain exactly K nodes.

sample

3 2 2
1 + 2
1 2
2 3

0