← 返回题目列表

Codeforces · 425/E

E. Sereja 和套装

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

假设集合 S 由 m 个不同的区间 [l1, r1], [l2, r2], ..., [lm, rm] 组成(1 ≤ li ≤ ri ≤ n;li、ri 是整数)。

假设 f(S) 是您可以从集合 S 中选择的间隔的最大数量,这样每两个间隔都不相交。我们假设,如果存在整数 x,并且满足两个不等式:l1 ≤ x ≤ r1 和 l2 ≤ x ≤ r2,则两个区间 [l1, r1] 和 [l2, r2] 相交。

Sereja 想知道,有多少个集合 S,使得 f(S) = k?以 1000000007 (109 + 7) 为模计算该数字。

输入

第一行包含整数 n, k (1 ≤ n ≤ 500; 0 ≤ k ≤ 500)。

输出

在一行中打印问题的答案,以 1000000007 (109 + 7) 为模。

示例

输入 #1

3 1

输出 #1

23

输入 #2

3 2

输出 #2

32

输入 #3

2 0

输出 #3

1

输入#4

2 2

输出#4

2