分数: 700 点
问题陈述
俳句是日本诗歌的一种简短形式。俳句由三个短语组成,依次为 5、7 和 5 个音节。
伊吕波正在寻找 X,Y,Z-俳句 整数序列中的 (定义如下)。
考虑所有长度的整数序列 N 其元素介于 1 和 10,包括在内。其中 10^N 序列,有多少个包含 X,Y,Z-俳句?
这里,一个整数序列 a_0, a_1, ..., a_{N-1} 据说 包含一个 X,Y,Z-俳句 整数序列中的 当且仅当存在四个索引 x, y, z, w (0 ≦ x < y < z < w ≦ N) 满足以下所有条件:
- a_x + a_{x+1} + ... + a_{y-1} = X
- a_y + a_{y+1} + ... + a_{z-1} = Y
- a_z + a_{z+1} + ... + a_{w-1} = Z
由于答案可能非常大,因此打印数字模 10^9+7.
约束
- 3 ≦ N ≦ 40
- 1 ≦ X ≦ 5
- 1 ≦ Y ≦ 7
- 1 ≦ Z ≦ 5
输入
输入由标准输入按以下格式给出:
N X Y Z
输出
打印包含 X,Y,Z-俳句,模数 10^9+7.
示例输入 1
3 5 7 5
示例输出 1
1
这里,唯一包含 5,7,5-俳句是 [5, 7, 5].
示例输入 2
4 5 7 5
示例输出 2
34
示例输入 3
37 4 2 3
示例输出 3
863912418
示例输入 4
40 5 7 5
示例输出 4
562805100