F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Separated Number

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 608    Accepted Submission(s): 242


Problem Description
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$.
 

Input
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$.
 

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

Sample Input
1 3 100
 

Sample Output
112
 

Hint
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.
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-03-28 18:28:45, Gzip enabled