D. Үзэсгэлэнтэй хос тоонууд

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Бүхэл $(a_{1}, b_{1}), (a_{2}, b_{2}), ..., (a_{k}, b_{k})$ гэсэн үзэсгэлэнтэй хос тоон дараалал байгаа. Энэ дараалал нь дараах нөхцлүүд хангах хэрэгтэй:

  • $1 ≤ a_{1} ≤ b_{1} < a_{2} ≤ b_{2} < ... < a_{k} ≤ b_{k} ≤ n$, ($n$ нь өгөгдсөн эерэг бүхэл тоо);
  • Бүх $b_{1} - a_{1}$, $b_{2} - a_{2}$, $...$, $b_{k} - a_{k}$ тоонууд давхцахгүй.

Өгөгдсөн $n$ тоог $k$ урттай үзэсгэлэнт дарааллаас олно. Хариу нь $1000000007$ $(10^{9} + 7)$-ээс их байж болохгүй.

Оролт

Эхний мөрөнд бүхэл $t$ ($1 ≤ t ≤ 2*10^{5}$) тоо агуулагдана. Энэ тоо нь тестийн өгөгдлийн тоо.

Дараагийн $t$ мөр бүрд хоёр бүхэл $n$ болон $k$ ($1 ≤ k ≤ n ≤ 1000$) тоонууд агуулагдана.

Гаралт

Оруулсан тест бүрийн хариултыг хэвлэхдээ модуляр $1000000007$ $(10^{9} + 7)$ дотор байна. Тестийн хариултуудийг хэвлэхдээ тестийн дарааллийн дагуу хэвлэнэ.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
6
1 1
2 1
2 2
3 1
3 2
3 3
Гаралт
1
3
0
6
2
0

Тэмдэглэл

Жишээний эхний тестэнд үзэсгэлэнт дараалал яг нэг $(1, 1)$ байна.

Жишээний хоёр дахь тестэнд үзэсгэлэнт дараалал дараах дарааллууд байна. Үүнд:

  • $(1, 1)$;
  • $(1, 2)$;
  • $(2, 2)$.

Жишээний дөрөв дахь тестэнд үзэсгэлэнт дараалал дараах дарааллууд байна. Үүнд:

  • $(1, 1)$;
  • $(1, 2)$;
  • $(1, 3)$;
  • $(2, 2)$;
  • $(2, 3)$;
  • $(3, 3)$.

Жишээний тав дахь тестэнд үзэсгэлэнт дараалал дараах дарааллууд юм. Үүнд:

  • $(1, 1), (2, 3)$;
  • $(1, 2), (3, 3)$.

Жишээний гурав дахь болон зургаа дахь тестэнд үзэсгэлэнт дараалал байхгүй байна.

Сэтгэгдлүүдийг ачааллаж байна...