问题 J: 吟诗(poetize)

问题 J: 吟诗(poetize)

时间限制: 1 Sec  内存限制: 256 MB
提交: 37  解决: 3
[提交][状态][讨论版][命题人:]

题目描述

"文章本天成,妙手偶得之。" 吟诗是表达情怀的常用手段,战争落下了帷幕,常年的军旅生活使得小虾米喜欢上了豪放 派的诗歌。 这一天,小虾米突然想吟诗了。著名的豪放派诗人苏轼有“老夫聊发少年狂,左牵黄,右 擎苍。”的豪放,又有“十年生死两茫茫,不思量,自难忘。”的悲怆。小虾米心向往之,于是也 想用《江城子》词牌名作诗。 小虾米想作出能流传千古的诗,根据经验,如果一首诗存在妙手就能流传千古。 具体来说,一首 N 个字的诗,每个字可以用 1 到 10 之间的某个正整数来表示。同时存在 三个正整数 X,Y,Z(1 ≤X≤ 7,1 ≤Y≤ 5,1 ≤Z≤ 5),如果诗中出现了三个连续的片段使得 第一个片段之和为 X,第二个片段之和为 Y,第三个片段之和为 Z,则小虾米认为这首诗出现 了妙手。

 即长度为 n 的序列 a1 , a2 . . . an (1 ≤ ai ≤ 10),如果存在 i,j, k,l (1 ≤i< j <k <l≤n 使得 ai+ a(i+1) + . . . a(j-1) = X 且 aj + a(j+1) + . . . a(k-1) =Y 且 ak + a(k+1) + . . .a(l-1) = Z 同时成立,则认为序列 出现了妙手(注:第二个片段紧接第一个片段,第三个片段紧接第二个片段)。

 举例来说,如果 N=7, X=7,Y=3,Z=3,则所有长度为 7 的序列中,很显然共有10^7种序 列,其中一种序列 [1, 5, 2, 2, 1, 3, 4] 出现了妙手,因为存在三个连续的区间 [2, 3]、[4, 5]、[6, 6] 满足它们的和分别为 X=7,Y=3,Z=3。 小虾米想知道在给定 N, X, Y, Z 的前提下(共计10^n 种序列,即共10^n 种诗),计算有多少 种存在妙手的诗,请你帮他计算出答案

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

输入

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

输出

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

样例输入

样例1
3 2 3 3
样例2
4 7 5 5
样例3
23 7 3 5

样例输出

样例1输出
1
样例2输出
34
样例3输出
824896638

提示


对于 30% 的数据,3≤ n≤ 5; 



对于 60% 的数据,3≤n≤20; 



对于 100% 的数据,3≤n≤40,1≤X≤7,1≤Y≤ 5,1≤Z≤5

[提交][状态]