AT_abc468_g.Restricted Permutation

You are given an integer $N$ and a string $S$ of length $N$ consisting of o and x.

Find the number, modulo $998244353$, of permutations $P=(P_1,P_2,\ldots,P_N)$ of $(1,2,\ldots,N)$ satisfying the following condition.

• For $k=1,2,\ldots,N$, the following two are equivalent.
  • $S_k=$ o
  • $P$ contains a permutation of $(1,2,\ldots,k)$ as a contiguous subsequence.

给定一个整数 $N$ 和一个长度为 $N$ 的字符串 $S$，其中仅包含字符 o 和 x。

求满足以下条件的排列 $P=(P_1,P_2,\ldots,P_N)$（即 $(1,2,\ldots,N)$ 的一个排列）的个数，答案对 $998244353$ 取模。

• 对于 $k=1,2,\ldots,N$，以下两个命题等价：
  • $S_k=$ o
  • $P$ 包含 $(1,2,\ldots,k)$ 的某个排列作为连续子序列。

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

$N$
$S$

输入从标准输入中按以下格式给出：

$N$
$S$

Output the answer.

输出答案。

Sample 1 Explanation:
$P=(1,3,2),(2,3,1)$ satisfy the condition.

Sample 2 Explanation:
There is no $P$ satisfying the condition.

Constraints

• $1\le N\le 2000$
• $S_i$ is a string of length $N$ consisting of o and x.

样例 1 解释：
满足条件的 $P$ 有 $(1,3,2)$ 和 $(2,3,1)$。

样例 2 解释：
不存在满足条件的 $P$。

约束条件

• $1\le N\le 2000$
• $S_i$ 是一个长度为 $N$ 的字符串，仅由字符 o 和 x 组成。