You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时空限制

1S/512M

题目描述

有 $n$ 个球排成一行，球的颜色分为白和黑两种。

进行 $n-1$ 轮合成，每一轮你选择两个位置相邻的球合成为一个新球，新球的颜色由你从合成前这两个球的颜色中选择。

分别求最终合成白球和黑球的不同合成方案各有多少种，对 $998244353$ 取模。如果两个方案，在某一轮合成选择的两个球的位置不同，或该轮合成的新球的颜色不同，视为两个不同合成方案。

格式

输入格式

第一行包含一个整数 $n$ 表示球的数量。

第二行包含一个仅由 w 和 b 组成的长度为 $n$ 的字符串 $S$ 表示每个球的颜色，其中 w 表示白球 b 表示黑球。

输出格式

输出一行包含两个整数，分别表示最终合成白球的不同合成方案数量和最终合成黑球的不同合成方案数量。

样例

样例输入 #1

3
wwb

样例输出 #1

3 2

样例解释 #1

最终合成白球的合成方案有 $3$ 种：

①第一轮将第 $1$ 个球和第 $2$ 个球合成为白球，第二轮将第 $1$ 个球和第 $2$ 个球合成为白球；

②第一轮将第 $2$ 个球和第 $3$ 个球合成为白球，第二轮将第 $1$ 个球和第 $2$ 个球合成为白球；

③第一轮将第 $2$ 个球和第 $3$ 个球合成为黑球，第二轮将第 $1$ 个球和第 $2$ 个球合成为白球。

最终合成黑球的合成方案有 $2$ 种：

①第一轮将第 $1$ 个球和第 $2$ 个球合成为白球，第二轮将第 $1$ 个球和第 $2$ 个球合成为黑球；

②第一轮将第 $2$ 个球和第 $3$ 个球合成为黑球，第二轮将第 $1$ 个球和第 $2$ 个球合成为黑球。

样例输入 #2

27
wwbwbwwbbwwbwbwwbbwwbwbwwbb

样例输出 #2

112681370 131030915

样例输入 #3

1
b

样例输出 #3

0 1

数据规模

对于 $20\%$ 的数据，$n\leq 10$。

另有 $20\%$ 的数据，$S$ 仅由 w 组成。

对于 $100\%$ 的数据，$1\leq n\leq 400$。数据保证 $S$ 仅由 w 和 b 组成。