{"problem":{"name":"[SNOI2022] 数位","description":{"content":"小 S 是一个喜欢数数的女孩子。 有一天，她在睡前躺在床上数数，当她数到 $977431$ 的时候，她终于困了，并且决定睡觉。但此时她突然发现这个数字的各位数码是单调不增的！她觉得这相当有趣，于是她又睡不着了。 她想知道有多少个数在 $L, R$ 之间，并且它的各位数码是单调不增的。但这个问题太无聊了。 她又想知道有多少数对 $(a, b)$ 在 $L, R$ 之间，并且 $(a + b)$","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":6000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8362"},"statements":[{"statement_type":"Markdown","content":"小 S 是一个喜欢数数的女孩子。\n\n有一天，她在睡前躺在床上数数，当她数到 $977431$ 的时候，她终于困了，并且决定睡觉。但此时她突然发现这个数字的各位数码是单调不增的！她觉得这相当有趣，于是她又睡不着了。\n\n她想知道有多少个数在 $L, R$ 之间，并且它的各位数码是单调不增的。但这个问题太无聊了。\n\n她又想知道有多少数对 $(a, b)$ 在 $L, R$ 之间，并且 $(a + b)$ 的各位数码是单调不增的。但这个问题也太无聊了。\n\n终于，她想到了一个有趣一些的问题：\n\n给定整数 $L, R, k$，求有多少个 $k$ 维向量 $(a_1, a_2, ..., a_k)$ 满足 $(a_1 + a_2 + ... + a_k)$ 的数码是单调不增的，并且 $\\forall i \\in [1, k],  L \\leq a_i \\leq R$。\n\n由于答案可能很大，请你输出它对 $998244353$ 取模的结果。\n\n## Input\n\n输入的第一行是一个正整数 $L$，含义见【题目描述】。\n\n输入的第二行是一个正整数 $R$，含义见【题目描述】。\n\n输入的第三行是一个正整数 $k$，含义见【题目描述】。\n\n## Output\n\n输出一行一个整数表示合法的向量数，答案 $998244353$ 取模。\n\n[samples]\n\n## Note\n\n**【数据规模与约定】**\n\n对于全部数据，$1 \\leq L \\leq R < 10^{1000}$，$1 \\leq k \\leq 50$。\n\n具体的数据规模与约定见下表。\n\n| 测试点编号 |    $R<$     | $k$  |\n| :--------: | :---------: | :--: |\n|    $1$     |   $10^6$    | $1$  |\n|    $2$     |   $10^6$    | $10$ |\n|    $3$     |   $10^6$    | $20$ |\n|    $4$     |   $10^6$    | $30$ |\n|    $5$     |   $10^6$    | $50$ |\n|    $6$     |  $10^{17}$  | $10$ |\n|    $7$     |  $10^{17}$  | $10$ |\n|    $8$     |  $10^{17}$  | $20$ |\n|    $9$     |  $10^{17}$  | $30$ |\n|    $10$    |  $10^{17}$  | $50$ |\n|    $11$    |  $10^{50}$  | $2$  |\n|    $12$    |  $10^{50}$  | $10$ |\n|    $13$    | $10^{100}$  | $2$  |\n|    $14$    | $10^{100}$  | $3$  |\n|    $15$    | $10^{100}$  | $10$ |\n|    $16$    | $10^{200}$  | $3$  |\n|    $17$    | $10^{200}$  | $10$ |\n|    $18$    | $10^{300}$  | $10$ |\n|    $19$    | $10^{300}$  | $10$ |\n|    $20$    | $10^{300}$  | $20$ |\n|    $21$    | $10^{500}$  | $10$ |\n|    $22$    | $10^{500}$  | $20$ |\n|    $23$    | $10^{1000}$ | $30$ |\n|    $24$    | $10^{1000}$  | $50$ |\n|    $25$    | $10^{1000}$  | $50$ |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8362","tags":["各省省选","2022","O2优化","陕西"],"sample_group":[["1\n100\n2","3728"],["19260817\n1000000000\n3","28745082"],["114514233\n1919810233\n10","135934411"],["样例 4 见附件 digit4.in","样例 4 见附件 digit4.ans"],["样例 5 见附件 digit5.in","样例 5 见附件 digit5.ans"]],"created_at":"2026-03-03 11:09:25"}}