Пусть множество S состоит из m различных интервалов [l₁, r₁], [l₂, r₂], ..., [l_m, r_m] (1 ≤ l_i ≤ r_i ≤ n; l_i, r_i — целые числа).

Пусть f(S) — максимальное количество интервалов, которое можно выбрать из множества S, чтобы среди них не было ни одной пары пересекающихся. Считается, что два интервала [l₁, r₁] и [l₂, r₂] пересекаются, если найдется целое число x, для которого выполняются неравенства: l₁ ≤ x ≤ r₁ и l₂ ≤ x ≤ r₂.

Сереже интересно: сколько существует таких множеств S, что f(S) = k? Посчитайте для него это количество по модулю 1000000007 (10⁹ + 7).