← 返回题单
题单练习 状态压缩DP
← 上一题 下一题 →

A6208 | 和風いろはちゃん

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

日本引以为傲的美丽韵律中，有一种叫做五七五。いろは酱决定在数列中寻找五七五。但这太简单了，于是她决定去寻找 XYZ。

给定一个长度为 $N$ 的数列 $a_0, a_1, \ldots, a_{N-1}$，其中每个元素的取值范围为 $1$ 到 $10$。这样的数列共有 $10^N$ 种可能。请问，其中包含 XYZ 的数列有多少种？

这里，包含 XYZ 被定义如下：

  • 存在 $0 \leq x y z w \leq N$，使得
- $a_x + a_{x+1} + \cdots + a_{y-1} = X$
- $a_y + a_{y+1} + \cdots + a_{z-1} = Y$
- $a_z + a_{z+1} + \cdots + a_{w-1} = Z$

请输出包含 XYZ 的数列个数。由于答案可能非常大，请输出对 $10^9+7$ 取模后的结果。

输入格式

输入从标准输入读取，格式如下：

$N$ $X$ $Y$ $Z$

输出格式

输出包含 XYZ 的数列个数，对 $10^9+7$ 取模后的结果。

输入输出样例

输入 #1
3 5 7 5
输出 #1
1
输入 #2
4 5 7 5
输出 #2
34
输入 #3
37 4 2 3
输出 #3
863912418
输入 #4
40 5 7 5
输出 #4
562805100
C++ 编辑器
输入
输出