Lát gạch 4

Điểm: 0,15 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 512M

Input: stdin

Output: stdout

Nguồn bài:

Thầy Ðỗ Ðức Ðông

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho một hình chữ nhật kích thước $2 \times N$ ( $1 \leq N < 10^{9}$ ). Hãy đếm số cách lát các viên gạch nhỏ kích thước $1 \times 2$ và $2 \times 1$ vào hình trên sao cho không có phần nào của các viên gạch nhỏ thừa ra ngoài, cũng không có vùng diện tích nào của hình chữ nhật không được lát.

Input

Gồm nhiều test, dòng đầu ghi số lượng test $T$ ( $T \leq 100$ ). $T$ dòng sau mỗi dòng ghi một số $N$ .

Output

Ghi ra $T$ dòng là số cách lát tương ứng lấy phần dư cho $111 539 786$ .

Sample Input

Copy

Sample Output

Copy

1
2
3

Bình luận

Hãy đọc nội quy trước khi bình luận.

-10

chunguyen2k8 đã bình luận 12:12:03 ch, 20/02/2024

nhân ma trận , ez :))

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-7

khieudung123 đã bình luận 3:10:14 sa, 29/08/2023

khó thí

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

1

trongtenlinhcbhk64 đã bình luận 8:46:32 sa, 16/05/2023

bài hay quá =))

-27

loingu1902 đã bình luận 7:19:36 sa, 18/10/2022 ← chỉnh sửa →

.

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-75

nngovannhhungg đã bình luận 8:11:13 sa, 15/01/2022

quá dễ :))

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.