题目描述

你有一个 $01$ 序列 $a$ 和两种操作：

1. 选择 $a_i<a_{i+1}$ 并删去 $a_{i+1}$。
2. 选择 $a_i<a_{i+1}$ 并交换这两个数。

你要进行若干次这两种操作（可以不进行），求结束时会得到多少种本质不同的序列？

对 $998244353$ 取模。

输入格式

本题有多组测试。第一行输入一个整数 $T$ 表示测试组数。

每组测试第一行输入一个整数 $n$。

下一行输入一个 $01$ 串，第 $i$ 个字符是 $a_i$。

输出格式

包含 $T$ 行，第 $i$ 行包含一个整数，表示结束时会得到多少种本质不同的序列。对 $998244353$ 取模。

3
2
01
3
111
3
010

3
1
3

提示

定义 $s$ 表示每组测试内 $a_i$ 之和的最大值。定义 $N$ 表示所有测试中 $n$ 的和。

对于所有数据，保证 $1\le T\le 10^3$，$1\le n,N\le 10^5$，$0\le s\le 2\times 10^3$。