#P3120. Line

    ID: 2275 传统题 1000ms 512MiB 尝试: 148 已通过: 62 难度: 8 上传者: 标签>CF2400提高+/省选-计数 DP对称性分析矩阵快速幂截断幂级数Pascal 递推zcwwzdjn提供

Line

题目描述

Wayne 喜欢排队……不对,是 Wayne 所在学校的校长喜欢看大家排队,尤其是在操场上站方阵。

某日课间操时,校长童心大发想了一个极具观赏性的列队方案,如下:

  1. 方阵排成 nn 行,每行恰好 mm 个学生。
  2. 由于校长喜欢女孩子,所以在一行上不能有连续 pp 个男生。
  3. 由于校长喜欢女孩子,所以在校长看来,一列全是男生是不好的,全男生的列数不能超过 qq。

Wayne 因为感冒了所以不用参加列队,不过他看着大家排队排得不亦乐乎,于是他想知道,在男女生数目无限制的情况下,有多少种列队方案? 两种方案被视作不同,表明存在至少一个二元组 (i,j)(i,j) 而两种方案中第 ii 行第 jj 列的同学性别不同。另外,因为答案可能很大,所以请把答案模 109+710^9 + 7。

输入格式

输入仅一行 44 个正整数,依次是 n,m,p,qn,m,p,q。

输出格式

输出仅一行,表示答案。

2 3 3 1
46

数据规模和约定

对于 5%5\% 的数据,p=1p = 1。

对于另外 10%10\% 的数据,n×m≤20n \times m \le 20。

对于另外 15%15\% 的数据,n≤2n \le 2,m≤106m \le 10^6。

对于另外 10%10\% 的数据,n≤2n \le 2。

对于另外 20%20\% 的数据,n≤4n\le 4,p≤2p \le 2,q≤2q\le 2。

对于 100%100\% 的数据,1≤n≤81 \le n \le 8,1≤m≤10181 \le m \le 10^{18},1≤p≤31 \le p \le 3,0≤q≤30 \le q \le 3。