Đếm số xâu nhị phân chứa 100
Submit solution
Points:
3
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
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á \(10^6\) 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 \(10^9+7\) (1000000007)
Ví dụ
Input
3
0
5
10Output
0
12
792
Comments
Mình sẽ làm 1 bài lại là cho n giới hạn tới \(10^{18}\)