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

Limits: 2 sec., 256 MiB

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

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

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

Input

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

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

Output

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

Constraints

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

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

Samples

Input (stdin) сopy	Output (stdout) сopy
2 2 2 2 0	4 1

Notes

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