#P11856. [CSP-J2022 山东] 吟诗
[CSP-J2022 山东] 吟诗
题目背景
受疫情影响,山东省取消了 CSP-J 2022 认证活动,并于次年三月重新命题,在省内补办比赛。
题目描述
"文章本天成,妙手偶得之。"
吟诗是表达情怀的常用手段,战争落下了帷幕,常年的军旅生活使得小虾米喜欢上了豪放派的诗歌。
这一天,小虾米突然想吟诗了。著名的豪放派诗人苏轼有“老夫聊发少年狂,左牵黄,右擎苍。”的豪放,又有“十年生死两茫茫,不思量,自难忘。”的悲怆。小虾米心向往之,于是也想用《江城子》词牌名作诗。
小虾米想作出能流传千古的诗,根据经验,如果一首诗存在妙手就能流传千古。
具体来说,一首 N 个字的诗,每个字可以用 到 之间的某个正整数来表示。同时存在三个正整数 ,如果诗中出现了三个连续的片段使得第一个片段之和为 ,第二个片段之和为 ,第三个片段之和为 ,则小虾米认为这首诗出现了妙手。
即长度为 的序列 $a_{1},a_{2},\dots a_{n} \left(1\le a_{i}\le10\right)$,如果存在 使得 且 且 同时成立,则认为序列出现了妙手(注:第二个片段紧接第一个片段,第三个片段紧接第二个片段)。
举例来说,如果 ,,,,则所有长度为 的序列中,很显然共有 种序列,其中一种序列 出现了妙手,因为存在三个连续的区间 、、 满足它们的和分别为 ,,。
小虾米想知道在给定 的前提下(共计 种序列,即共 种诗),计算有多少种存在妙手的诗,请你帮他计算出答案。
由于答案可能很大,请你将结果对 取模。
输入格式
一行,以空格隔开的 4 个正整数 ,分别表示序列长度和题目中 的值。
输出格式
一行,一个整数,表示答案对 取模的结果。
3 2 3 3
1
4 7 5 5
34
23 7 3 5
824896638
提示
样例一说明
在所有可能的序列中,只能构造出一种序列 满足题意,因此答案为 。
数据范围
对于 的数据,;
对于 的数据,;
对于 的数据,。