Тарас та математика

Обмеження: 2 сек., 256 МіБ

Сьогодні Тарас придумав нову задачу.

Задано два цілих числа \(n\) і \(p\).

Обчисліть \(s = C_n^0 + C_n^1 + \dots + C_n^p\) за модулем простого числа \(10^9+7\).

Вхідні дані

Перший рядок містить ціле число \(t\) — кількість тестів.

Кожен з наступних \(t\) рядків містить два числа \(n\) та \(p\).

Вихідні дані

Для кожного тесту в окремому рядку виведіть ціле число — \(s\) за модулем \(10^9+7\).

Обмеження

\(1 \le t \le 10^3\),

\(1 \le p \le n \le 10^3\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
2 2 2 2 0	4 1

Примітки

У першому тесті \(s = C_2^0 + C_2^1 + C_2^2 = 1 + 2 + 1 = 4\).