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

Points: 4

Time limit: 1.0s

Memory limit: 98M

Author:

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$ )