Leo cầu thang

Dễ

quy hoạch động3 test · 3 giây

Cầu thang có n bậc, mỗi bước bạn leo 1 hoặc 2 bậc. Có bao nhiêu cách leo lên bậc trên cùng? In kết quả mod 1 000 000 007.

Dữ liệu vào

Dòng 1: t (1 ≤ t ≤ 10⁵).

t dòng, mỗi dòng một số n (1 ≤ n ≤ 10⁶).

t dòng.

Input

Output

1
2
8

# Đọc dữ liệu từ input(), in kết quả bằng print()
import sys

def main():
    data = sys.stdin.read().split()
    # TODO: xử lý


main()

# Đọc dữ liệu từ input(), in kết quả bằng print()
import sys

def main():
    data = sys.stdin.read().split()
    # TODO: xử lý


main()

Input (stdin)

Output

Bấm “Chạy thử” để xem kết quả với input bên trái.