0689 String Rotation

We define a string as a 0689-string if it consists only of the digits 0, 6, 8 and 9. Given a 0689-string s of length n, you must perform exactly one operation: select a non‐empty substring of s and rotate it 180 degrees.

More formally, let s_i be the i-th character of s. After rotating the substring from index l to r (1 ≤ l ≤ r ≤ n), the new string t is defined as follows:

$$ t_i = \begin{cases} s_i & \text{if } 1 \le i < l \text{ or } r < i \le n, \\[6pt] \mathtt{0} & \text{if } l \le i \le r \text{ and } s_{l+r-i} = \mathtt{0}, \\[6pt] \mathtt{6} & \text{if } l \le i \le r \text{ and } s_{l+r-i} = \mathtt{9}, \\[6pt] \mathtt{8} & \text{if } l \le i \le r \text{ and } s_{l+r-i} = \mathtt{8}, \\[6pt] \mathtt{9} & \text{if } l \le i \le r \text{ and } s_{l+r-i} = \mathtt{6}. \end{cases} $$

Your task is to determine the number of different strings that can be obtained after performing the operation exactly once.

inputFormat

The first line contains an integer n (1 ≤ n ≤ 1000), the length of the string. The second line contains a 0689-string s of length n.

outputFormat

Output a single integer: the number of distinct strings that can be obtained after performing the operation exactly once.

sample

4
6089

8