Circuit Failure Probability

In this problem, you are given a circuit composed of up to \( N \) components, where \( 1 \le N \le 26 \). Each component is represented by a capital letter: component 1 by A, component 2 by B, and so on. Each component \( i \) fails (i.e. becomes disconnected) with probability \( p_i \) (\( 0 \le p_i \le 1 \)).

The circuit is built by connecting smaller circuits in two ways:

• Series Connection: A series circuit is formed by connecting circuits one after another. The series connection of \( K \) circuits is represented by concatenating the circuits (e.g. ABCD). The series circuit fails if any one of its subcircuits fails. Thus, if the failure probabilities are \( f_1, f_2, \dots, f_K \), the failure probability of the series circuit is given by \[ f_{series} = 1 - \prod_{i=1}^{K} (1 - f_i). \]
• Parallel Connection: A parallel circuit is formed by placing circuits in parallel. The parallel connection of \( K \) circuits is represented by writing each circuit within its own pair of parentheses consecutively. For example, (A)(BC) represents a parallel circuit with two branches: the first branch is a single component circuit A, and the second branch is a series circuit consisting of B and C. A parallel circuit fails only if all its branches fail. Hence, if the failure probabilities of the branches are \( f_1, f_2, \dots, f_K \), the failure probability is \[ f_{parallel} = \prod_{i=1}^{K} f_i. \]

A base circuit is simply a single component represented by its corresponding letter. When components are written consecutively without parentheses, they form a series circuit. When several circuits are each enclosed in their own pair of parentheses and written consecutively, they form a parallel circuit.

Your task is to compute the failure probability (i.e. the probability that the circuit becomes open) of the given circuit.

inputFormat

The input consists of the following lines:

1. An integer \( N \) (\( 1 \le N \le 26 \)), denoting the number of components.
2. A string representing the circuit structure. Note:
   • A single component is represented by a capital letter (A for component 1, B for component 2, etc.).
   • Components written consecutively (without extra parentheses) form a series circuit.
   • If several circuits are written as consecutive groups enclosed in parentheses (e.g. (A)(BC)), they form a parallel circuit.
3. \( N \) floating-point numbers representing the failure probabilities \( p_1, p_2, \dots, p_N \) for components A, B, ..., respectively.

There are no extra spaces in the circuit expression.

outputFormat

Output a single floating-point number representing the failure probability of the circuit. Your answer will be considered correct if its absolute or relative error does not exceed \(10^{-6}\).

sample

2
AB
0.5 0.5

0.75