Problem Statement

You are given a positive integer $N$, a string $S$ of length $N$ consisting of # and ., and a length-$N$ sequence of positive integers $R=(R_1,R_2,\dots,R_N)$.

There is a forest with $N$ sections arranged in a single horizontal line. The sections are numbered $1,2,\dots,N$ from left to right.

Some sections have trees. Specifically, section $i$ has a tree if and only if the $i$-th character of $S$ is #. It is guaranteed that the following operation can be performed at least once.

You can repeat the following operation as many times as you like:

• Choose two sections without trees. Let sections $i$ and $j$ (where $i < j$) be the chosen sections from left to right. Then, all trees between sections $i$ and $j$ are removed, and you gain a reward of $R_i+R_j$.

Here, you cannot perform an operation that removes no trees.

Find the number of ways to perform the first operation to achieve the maximum possible total reward. Two ways are considered distinct if and only if there exists a section chosen in one way but not in the other.

Constraints

• $3\leq N\leq 2\times 10^5$
• The length of $S$ is $N$, and each character is # or ..
• $1\leq R_i\leq 10^9$ $(1\leq i\leq N)$
• The operation can be performed at least once.
• $N$ and $R_i$ are integers.

Input

The input is given from Standard Input in the following format:

N
S
R_1 R_2 \dots R_N

Output

Output the answer.