C. 不等关系

内存限制:512 MiB 时间限制: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

35

样例说明 1

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

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

样例输入 2

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

样例输出 2

497133532

数据范围与提示

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

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