题目描述

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

样例 2

输入

4 5 7 5

输出

34

样例 3

输入

37 4 2 3

输出

863912418

样例 4

输入

40 5 7 5

输出

562805100

说明/提示

限制条件

• $3 \leq N \leq 40$
• $1 \leq X \leq 5$
• $1 \leq Y \leq 7$
• $1 \leq Z \leq 5$

样例解释 1

只有数列 $\{5,7,5\}$ 满足条件。

由 ChatGPT 4.1 翻译