Random Switch Toggling

Jiutiao Kelian is a playful girl. One day, she and her friend Fahai went to a room escape game. In front of them there are \( n \) switches, all initially off. To pass the level, the switches must match a target configuration given as a binary array \( s \) of length \( n \): if \( s_i = 0 \) then the \( i \)th switch must be off at the end; if \( s_i = 1 \) then it must be on.

Since they do not know \( s \), they resort to randomly pressing switches. Each switch \( i \) is assigned a positive weight \( p_i \). In every round, they choose a switch to press with probability \[ \frac{p_i}{\sum_{j=1}^{n} p_j}, \] independently each round. Pressing a switch toggles its state (off becomes on, and on becomes off). The process stops immediately when the current configuration exactly equals \( s \).

Being extremely lucky, Jiutiao managed to open the door exactly after pressing switches \( \sum_{i=1}^{n} s_i \) times. To appreciate her luck, she asks you to compute the expected number of presses required to pass the level using this random pressing method.

Note: It is guaranteed that \( n \le 20 \).

inputFormat

The first line contains an integer \( n \) \((1 \le n \le 20)\), representing the number of switches.

The second line is a string of length \( n \) consisting of characters '0' and '1', representing the target configuration \( s \). Here, '1' means the corresponding switch should be on, and '0' means off.

The third line contains \( n \) positive integers \( p_1, p_2, \dots, p_n \) (each \( p_i > 0 \)), which are the weights assigned to each switch.

outputFormat

Output the expected number of presses needed to achieve the target configuration. The answer should be printed with at least 6 decimal places of precision.

sample

1
1
5

1.000000