← 返回比赛
已结束 GESP巅峰赛#26
← 上一题 下一题 →

A5303 | 奇怪的探针

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

$Alice$ 参加了一场奇怪的比赛。
比赛中，每条赛道都有一条长度为 $n$ 的信号轨。现在 Alice 有 $n$ 个不同强度的探针，需要将它们一一放置到位置 $1\ldots n$ 上
比赛给出了一些要求：对若干内点 $i$（$2\le i\le n-1$），规定其局部形态必须满足下述之一：

* 顶型要求 P：位置 $i$ 处必须是 $\{a_{i-1},a_i,a_{i+1}\}$ 中的严格最大；
* 底型要求 V：位置 $i$ 处必须是 $\{a_{i-1},a_i,a_{i+1}\}$ 中的严格最小。

边界位置不会有要求，同一位置也不会同时提出两类要求。除此之外，不再施加其他限制。

比赛组织者准备了多条赛道（多组数据）。Alice 想知道：对每条赛道，有多少种不同的强度布置方案满足全部要求？请你帮她计算，并将答案对 $998244353$ 取模。

输入格式

第一行一个整数 $t$（测试组数）。

接下来对每组测试：
* 第一行一个整数 $n$（信号轨长度）。
* 第二行一个长度为 $n$ 的字符串 $s$，表示每个位置的形态要求：

* '.' 表示该位置无要求；
* 'P' 表示该位置有顶型要求；
* 'V' 表示该位置有底型要求。

保证 $s_1 = s_n = '.'$，且输入不会出现同一位置同时为两类探针的矛盾描述。

输出格式

对每组测试输出一行一个整数，表示满足约束的方案数对 $998244353$ 取模的结果。

输入输出样例

输入 #1
3
5
.P.P.
5
.PVP.
10
..........
输出 #1
16
16
3628800
C++ 编辑器
输入
输出