数位的关系

对于一个十进制非负整数 $ n $，我们可以按照从高位到低位将其写成一个由数位 $ \texttt 0\sim \texttt 9 $ 构成的字符串 $ S(n) $（不含前导 $ 0 $）。

称一个仅由 $ \texttt < $ 和 $ \texttt > $ 组成的串为关系串。对于一个长度为 $ k $ 的关系串 $ R=r_1r_2\cdots r_k $ 和一个长度为 $ k+1 $ 的字符串 $ S=s_1s_2\cdots s_{k+1} $，如果任意 $ 1\leq i\leq k $，都有关系 $ r_i(s_i,s_{i+1}) $ 成立，则称字符串 $ S $ 满足关系串 $ R $ 的限制。

其中关系 $ r_i(s_i,s_{i+1}) $ 成立只有两种情况，$ r_i=\texttt{<} $ 且 $ s_i < s_{i+1} $ 或者 $ r_i=\texttt{>} $ 且 $ s_i > s_{i+1} $，比较按照字典序顺序。

现在定义 $ f(n,R) $ 表示 $ S(n) $ 中有多少个子序列满足关系串 $ R $ 的限制。给定 $ l,r,R $，求：
$$
\left(\sum_{n=l}^{r}f(n,R)\right) \bmod 998244353
$$

其中一个字符串的子序列定义为从原字符串中删去若干个（可以不删或删空）字符得到的新字符串。

本题单个测试点内包含多组测试数据。

第一行一个整数 $ T(1\leq T\leq 10) $，表示数据组数。

对于每组数据，第一行两个整数 $ l,r $ $ (1\leq l\leq r< 10^{500}) $，意义如题。

第二行一个关系串 $ R $ $ (1\leq |R|\leq 500) $，意义如题。

对于每组数据输出 $ q $ 行，每行一个整数表示答案。

5
12435 12435
<<
114514 114514
<><
1919810 1919810
<><>
1234 4321
<>
114514 1919810
<>>

7
5
5
4628
4377883

2024“钉耙编程”中国大学生算法设计超级联赛（1）