← 返回题目列表

Codeforces · 182/E

E. 木栅栏

中文机器翻译题面 查看原题

Vasya 最近买了一些土地,并决定用木栅栏围起来。

他去了一家名为“木板”的公司,生产栅栏用木板。 Vasya 阅读了该公司拥有的不同类型木材的产品目录。该公司使用第 i 种木材来生产这种类型的板材,即矩形 ai by bi 块。

Vasya 决定在这家公司订购板材并用它们建造围栏。原来,公司的仓库太大了,Vasya可以订购任意数量的每种类型的板材。请注意,瓦夏在建造栅栏时可以转动木板。然而,瓦夏不能转动方板。

Vasya 需要建造一个长度为 l 的栅栏,但是任意栅栏都做不到。瓦夏希望他的栅栏看起来很漂亮。当且仅当满足以下两个条件时,我们才会说栅栏是美丽的:

- 没有两个连续的相同类型的板
- 栅栏的第一块板具有任意长度,后续每块板的长度等于前一块的宽度

换句话说,如果栅栏中第i块板的类型与第i-1块板的类型不同,则栅栏被认为是漂亮的;此外,第 i 个板的长度等于第 i - 1 个板的宽度(对于所有 i,从 2 开始)。

现在 Vasya 想知道,为他的土地布置围栏的方式有多少种。你的任务是数出长度为 l 的不同美丽栅栏的数量。

如果对应的栅栏板类型和旋转顺序相同,则认为两个栅栏相同,否则栅栏不同。由于所求的数字可能足够大,因此您需要以 1000000007 (109 + 7) 为模来计算答案。

输入

第一行包含两个整数 n 和 l (1 ≤ n ≤ 100, 1 ≤ l ≤ 3000) — 相应的不同板类型的数量和栅栏长度。接下来的 n 行包含棋盘类型的描述:第 i 行包含两个整数 ai 和 bi (1 ≤ ai, bi ≤ 100) — 第 i 种棋盘的尺寸。行上的所有数字均以空格分隔。

输出

打印一个整数 — 所寻求的变体数量以 1000000007 (109 + 7) 为模。

示例

输入 #1

2 3
1 2
2 3

输出 #1

2

输入 #2

1 2
2 2

输出 #2

1

输入 #3

6 6
2 1
3 2
2 5
3 3
5 1
2 1

输出 #3

20

注意

在第一个示例中,有两种布置长度为 3 的漂亮栅栏的变体:

- 作为第一块栅栏板,使用长度为 1 和宽度 2 的第一种类型的板。作为第二块栅栏板,使用长度为 2 和宽度 3 的第二种类型的板。
- 转动后使用第二种类型的一块板。这使得它的长度等于 3,宽度等于 2。