Problem Description

There are $2N$ seats arranged in a circle, numbered $1,2,\ldots,2N$ in clockwise order.

For each $i$ ($1\le i\le 2N-1$), seats $i$ and $i+1$ are neighbours. Seats $1$ and $2N$ are also neighbours.

For each $i$ ($1\le i\le N$), seats $i$ and $i+N$ are opposite each other.

Some of the seats are occupied. For each $i$ ($1\le i\le 2N$), seat $i$ is occupied by exactly one person if $S_i$ is o, and is empty if $S_i$ is x.

You want to form pairs of people subject to the following conditions.

• Each person belongs to at most one pair.
• Each pair consists of two people seated in neighbouring or opposite seats.

Find the maximum possible number of pairs and the number of ways to achieve this maximum.

Two ways of forming pairs are considered different if their sets of unordered pairs differ.

Input Format

The input consists of a single test case of the following format.

N
S

The first line contains an integer $N$ ($1\le N\le 10^6$).

The second line contains a string $S$ of length $2N$ consisting of o and x.

Output Format

Print two integers separated by a space.

The first integer is the maximum possible number of pairs.

The second integer is the number of ways to achieve this maximum, modulo $998\,244\,353$.

3
ooxoxx

1 2

2
oooo

2 3

4
xxxxxxxx

0 1