575 「LibreOJ NOI Round #2」不等关系

内存限制:512 MB 时间限制:2000 ms

题目描述

给定一个字符串 $s_1, s_2, \ldots, s_n$ ,仅包含 < 和 > 两种字符。

你需要计算「使得 $p_i < p_{i+1}$ 当且仅当 $s_i$ 为 < 的排列 $p_1, p_2, \ldots, p_{n+1}$」的数量。

可以发现,答案可能很大,因此你只要输出它对 $998244353$ 取模的结果。

输入格式

从标准输入读入数据。

输入一行一个由 < 和 > 组成的字符串 $s_1, s_2, \ldots, s_n$。

输出格式

输出到标准输出。

输出一行一个整数,表示满足要求的排列数量对 $998244353$ 取模的结果。

样例 1

举例来说,排列 $(1,6,2,5,4,3)$ 是一个的满足要求的排列。

而排列 $(1,2,5,6,4,3)$ 不是一个的满足要求的排列,因为它不满足 $p_2>p_3$ 。

样例 2

数据范围与提示

对于所有测试数据,保证 $1 \leq n \leq 10^5$,$s_i\in{\mathtt{<},\mathtt{>}}$。

子任务编号 分值 $n$ 特殊性质
1 5 $\leq 8$ 无
2 5 $\leq 20$ 无
3 10 $\leq 200$ $s_i \neq s_{i+1}$
4 5 $\leq 200$ 无
5 10 $\leq 2000$ $s_i \neq s_{i+1}$
6 5 $\leq 2000$ 无
7 10 $\leq 100\,000$ $s_i \neq s_{i+1}$
8 50 $\leq 100\,000$ 无

样例

样例输入 1

<><>>

样例输出 1

35

样例输入 2

<><<>>><><<><>>

样例输出 2

497133532