题目描述

在一个遥远的银河系里，有一个由高级人工智能统治的星球。人工智能有一种特别的方式进行交流，那就是通过发送由 0 和 1 组成的信号串。他们的语言并不像人类的语言那样复杂，但却有一种独特的规则：在一条信号串中，0 和 1 都必须以连续的一组出现，且每组 0 的数量必须是 $x$，每组 1 的数量必须是 $y$。这样的信号串被称为“好的信号串”。

你的任务是，给定四个整数 $l$、$r$、$x$、$y$，求出长度为 $l$ 到 $r$ 区间内有多少个“好的信号串”，答案可能比较大你需要对$10^9+7$取模。

输入格式

输入包含一行，四个整数，分别表示 $l$、$r$、$x$、$y$ 。

输出格式

输出一个整数，表示长度为 $l$ 到 $r$ 区间内的“好的信号串”的数量。

2 5 2 3

5

1 10 3 3

14

说明/提示

"好的信号串"必须是连续的，并且0和1不能交替出现。例如，"010"或"101"都不是“好的信号串”。

样例解释 #1

在第一个例子中，长度为 2 的好的信号串有一个，即"00"；长度为 3 的好的信号串有一个，即"111"；长度为 4 的好的信号串有一个，即"0000"；长度为 5 的好的信号串有两个，即"00111"和"11100"。因此，总的“好的信号串”数量为5。

数据范围

每组数据点 $10$ 分，共 $10$ 组数据。

大样例

大样例下载