← 返回题目列表

AtCoder · arc058_c

E. 伊吕波和俳句

中文机器翻译题面 查看原题

分数: 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