#1170. 恋恋的中等题

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Komeiji Koishi

题目描述

渡渡鸟幼儿园的小朋友都知道,长度为nn的数列,其中每个数字都是1101-10之间的整数,这样的数列一共有10n10^n

那么在这些数列中,有多少个数列aa,能够满足存在1x<y<z<wn+11\leq x<y<z<w\leq n+1,使得:

i=xy1ai=P\sum_{i=x}^{y-1}a_i=P

i=yz1ai=Q\sum_{i=y}^{z-1}a_i=Q

i=zw1ai=R\sum_{i=z}^{w-1}a_i=R

输出满足条件的aa的个数,答案模109+710^9+7输出

输入格式

一行四个正整数n,P,Q,Rn,P,Q,R

输出格式

一行一个非负整数表示答案模109+710^9+7的结果

样例

样例输入1

5 4 5 4

样例输出1

543

样例输入2

3 2 4 2

样例输出2

1

样例输入3

38 5 7 5

样例输出3

545809677

数据范围与提示

1n401\leq n\leq 40

1P,R51\leq P,R\leq 5

1Q71\leq Q\leq 7