Separated Number

Cathy loves numbers, and recently she fell in love with the separation of numbers.

A separation of a number is defined as dividing the number into contiguous parts. For example, we can call ($11$)($451$)($4$) a separation of the number $114514$. The value of one separation is the sum of all the separated parts(the value of ($11$)($451$)($4$) equals to $11$+$451$+$4$=$466$). If one part has leading zeros, it is also valid, so the separation ($1$)($00$) of number $100$ is a valid separation too. Now Cathy has a number $x$ without leading zeros, and she wants to know the total value of separations which divide the number into no more than $k$ parts. She is not quite smart so she asked you for help.

Since the answer may be very large, you only need to output the answer modulo $998244353$.

The first line contains a number $T$($1 \leq T \leq 5$), the number of testcases.

For each testcase, there are two lines.
The first line contains a number $k$, the maximum number of parts.
The second line contains a number $x$, the queried number.

Let $n$ be the number of digits of $x$, and we will have $1 \leq n \leq 10^6$ and $1 \leq k \leq n$.

It is guaranteed that for all testcases, $\sum{n} \leq 10^6$.

For each testcase, output one number in one line, the answer modulo $998244353$.

1
3
100

112

In the sample, there are 4 possible separations with no more than 3 parts, (100),(1)(00),(10)(0),(1)(0)(0), and their values are 100, 1+0=1, 10+0=10, 1+0+0=1 respectively, so the answer will be 100+1+10+1=112.

2021“MINIEYE杯”中国大学生算法设计超级联赛（8）