A14651. Kuzya and Homework

Kuzya started going to school. He was given math homework in which he was given an array $a$ of length $n$ and an array of symbols $b$ of length $n$ , consisting of symbols '\*' and '/'.

Let's denote a path of calculations for a segment $[l; r]$ ( $1 \le l \le r \le n$ ) in the following way:

- Let $x=1$ initially. For every $i$ from $l$ to $r$ we will consequently do the following: if $b_i=$ '\*', $x=x*a_i$ , and if $b_i=$ '/', then $x=\frac{x}{a_i}$ . Let's call a path of calculations for the segment $[l; r]$ a list of all $x$ that we got during the calculations (the number of them is exactly $r - l + 1$ ).

For example, let $a=[7,$ $12,$ $3,$ $5,$ $4,$ $10,$ $9]$ , $b=[/,$ $*,$ $/,$ $/,$ $/,$ $*,$ $*]$ , $l=2$ , $r=6$ , then the path of calculations for that segment is $[12,$ $4,$ $0.8,$ $0.2,$ $2]$ .

Let's call a segment $[l;r]$ simple if the path of calculations for it contains only integer numbers.

Kuzya needs to find the number of simple segments $[l;r]$ ( $1 \le l \le r \le n$ ). Since he obviously has no time and no interest to do the calculations for each option, he asked you to write a program to get to find that number!

The first line contains a single integer $n$ ( $2 \le n \le 10^6$ ).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $1 \le a_i \le 10^6$ ).

The third line contains $n$ symbols without spaces between them — the array $b_1, b_2 \ldots b_n$ ( $b_i=$ '/' or $b_i=$ '\*' for every $1 \le i \le n$ ).

Print a single integer — the number of simple segments $[l;r]$ .