#1170. 恋恋的中等题

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

题目描述

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

那么在这些数列中,有多少个数列,能够满足存在,使得:

输出满足条件的的个数,答案模输出

输入格式

一行四个正整数

输出格式

一行一个非负整数表示答案模的结果

样例

样例输入1

5 4 5 4

样例输出1

543

样例输入2

3 2 4 2

样例输出2

1

样例输入3

38 5 7 5

样例输出3

545809677

数据范围与提示