题目描述

有 $2N$ 个座位排成一圈，按顺时针顺序编号为 $1,2,\ldots,2N$。

对于每个 $i$（$1\le i\le 2N-1$），座位 $i$ 和 $i+1$ 相邻。座位 $1$ 和 $2N$ 也相邻。

对于每个 $i$（$1\le i\le N$），座位 $i$ 和 $i+N$ 相对。

部分座位上坐着人。对于每个 $i$（$1\le i\le 2N$），若 $S_i$ 为 o，则座位 $i$ 上恰好坐着一个人；若 $S_i$ 为 x，则该座位为空。

你想将这些人配对，要求满足以下条件：

• 每个人至多属于一对。
• 每对中的两个人分别坐在相邻或相对的座位上。

求最多能组成多少对，以及达到这个最大值的方案数。

若两种配对方案对应的无序对集合不同，则认为它们是不同的方案。

输入格式

输入包含一组测试数据，格式如下：

N
S

第一行包含一个整数 $N$（$1\le N\le 10^6$）。

第二行包含一个长度为 $2N$、仅由 o 和 x 组成的字符串 $S$。

输出格式

输出两个整数，以一个空格分隔。

第一个整数为最多能组成的对数。

第二个整数为达到这个最大值的方案数，对 $998\,244\,353$ 取模。

3
ooxoxx

1 2

2
oooo

2 3

4
xxxxxxxx

0 1