Đếm số xâu nhị phân mà số chữ số 0 không ít hơn số chữ số 1

Submit solution
Points: 4
Time limit: 1.0s
Memory limit: 98M
Author:
TICHPX
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Thầy Tichpx dạy thuật toán sinh các xâu nhị phân độ dài \(n\) Thầy yêu cầu Tito lập trình đếm số xâu nhị phân có độ dài \(n\) mà số chữ số 0 không ít hơn số chữ số 1. Tito code non tay nên anh em hướng dẫn Tito nhé

Input

Dòng đầu gồm số bộ kiểm thử \(t\) là số nguyên dương có giá trị không vượt quá \(10^5\)

Dòng tiếp theo chứa \(t\) số nguyên dương có giá trị không vượt quá \(10^5\)

Output

Gồm \(t\) dòng mỗi dòng là một kết quả tương ứng với từng bộ kiểm thử, nhưng do kết quả quá lớn nên chỉ lấy phần dư khi chia cho 1000000007 (\(10^9+7\))

Ví dụ

Input

3
5 6 10

Output

16
42
638
tichpx

Comments