Đếm số xâu nhị phân chứa 100

Submit solution
Points: 3
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

Hệ nhị phân là một hệ đếm quen thuộc trong lập trình. Hôm nay thầy Tichpx dạy thuật toán sinh các dãy nhị phân độ dài n, Thầy có bài tập như sau: Đếm số xâu nhị phân có độ dài n và chứa xâu con "100", anh em hãy làm nhanh và nộp đáp án cho thầy nhé

Input

Dòng đầu là số bộ kiểm thử t là một số nguyên dương không quá 100

Tiếp theo t dòng mỗi dòng chứa một số nguyên không âm n có giá trị không vượt quá 106 là độ dài xâu nhị phân

Output

Gồm t dòng mỗi dòng là số xâu nhị phân có độ dài n và trong xâu phải chứa ít nhất một xâu con "100" vì số xâu quá lớn nên chỉ lấy phần dư của kết quả chia cho 109+7 (1000000007)

Ví dụ

Input

Copy
3
0
5
10

Output

Copy
0
12
792
tichpx

Comments


  • 2
    TICHPX  commented on May 1, 2023, 8:32 a.m.

    Mình sẽ làm 1 bài lại là cho n giới hạn tới 1018