#P11856. [CSP-J2022 山东] 吟诗

    ID: 10227 远端评测题 2000ms 512MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>2022山东枚举状态合并进制CSP-J 入门级

[CSP-J2022 山东] 吟诗

题目背景

受疫情影响,山东省取消了 CSP-J 2022 认证活动,并于次年三月重新命题,在省内补办比赛。

题目描述

"文章本天成,妙手偶得之。"

吟诗是表达情怀的常用手段,战争落下了帷幕,常年的军旅生活使得小虾米喜欢上了豪放派的诗歌。

这一天,小虾米突然想吟诗了。著名的豪放派诗人苏轼有“老夫聊发少年狂,左牵黄,右擎苍。”的豪放,又有“十年生死两茫茫,不思量,自难忘。”的悲怆。小虾米心向往之,于是也想用《江城子》词牌名作诗。

小虾米想作出能流传千古的诗,根据经验,如果一首诗存在妙手就能流传千古。

具体来说,一首 N 个字的诗,每个字可以用 111010 之间的某个正整数来表示。同时存在三个正整数 X,Y,Z(1X7,1Y5,1Z5)X,Y,Z\left(1\le X\le7,1\le Y\le5,1\le Z\le5\right),如果诗中出现了三个连续的片段使得第一个片段之和为 XX,第二个片段之和为 YY,第三个片段之和为 ZZ,则小虾米认为这首诗出现了妙手

即长度为 nn 的序列 $a_{1},a_{2},\dots a_{n} \left(1\le a_{i}\le10\right)$,如果存在 i,j,k,l(1i<j<k<ln)i,j,k,l\left(1\le i<j<k<l\le n\right) 使得ai+ai+1+aj1=Xa_{i}+a_{i+1}+\dots a_{j-1}=Xaj+aj+1+ak1=Ya_{j}+a_{j+1}+\dots a_{k-1}=Yak+ak+1+al1=Za_{k}+a_{k+1}+\dots a_{l-1}=Z 同时成立,则认为序列出现了妙手(注:第二个片段紧接第一个片段,第三个片段紧接第二个片段)。

举例来说,如果 N=7N=7X=7X=7Y=3Y=3Z=3Z=3,则所有长度为 77 的序列中,很显然共有 10710^{7} 种序列,其中一种序列 [1,5,2,2,1,3,4]\left[1,5,2,2,1,3,4\right] 出现了妙手,因为存在三个连续的区间 [2,3]\left[2,3\right][4,5]\left[4,5\right][6,6]\left[6,6\right] 满足它们的和分别为 X=7X=7Y=3Y=3Z=3Z=3

小虾米想知道在给定 N,X,Y,ZN,X,Y,Z 的前提下(共计 10n10^{n} 种序列,即共 10n10^{n} 种诗),计算有多少种存在妙手的诗,请你帮他计算出答案。

由于答案可能很大,请你将结果对 998244353998244353 取模。

输入格式

一行,以空格隔开的 4 个正整数 N,X,Y,ZN,X,Y,Z,分别表示序列长度和题目中 X,Y,ZX,Y,Z 的值。

输出格式

一行,一个整数,表示答案对 998244353998244353 取模的结果。

3 2 3 3
1
4 7 5 5
34
23 7 3 5
824896638

提示

样例一说明

在所有可能的序列中,只能构造出一种序列 [2,3,3]\left[2,3,3\right] 满足题意,因此答案为 11

数据范围

对于 30%30\% 的数据,3N53\le N\le5

对于 60%60\% 的数据,3N203\le N\le20

对于 100%100\% 的数据,3N40,1X7,1Y5,1Z53\le N\le40,1\le X\le7,1\le Y\le5,1\le Z\le5