2025 THT bảng B - Buổi 25 - Contest Thi thử số 1

Đề bài nằm ở trong bài 1 - notes.

Tham gia vào kỳ thi ôn tập TS10 2025 - Contest #1 để đọc đề.

Đề bài nằm ở trong bài 1 - notes.

Tham gia vào kỳ thi ôn tập TS10 2025 - Contest #1 để đọc đề.

Đề bài nằm ở trong bài 1 - notes.

Tham gia vào kỳ thi ôn tập TS10 2025 - Contest #1 để đọc đề.

Cho một hình chữ nhật kích thước \(2 \times N (1\le N\le 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\le 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 111539786.

Example

3    
1
2
3

1
2
3

Nguồn: https://vn.spoj.com/problems/LATGACH4/

Bờm đang nghiên cứu mực nước biển ở hành tinh Quạt Mo. Sau nhiều ngày theo dõi, Bờm nhận thấy rằng quy luật của mực nước biển là: mực nước biển của một ngày bất kì bằng trung bình cộng mực nước biển của ngày hôm trước và ngày hôm sau. Dựa vào ghi chép mực nước biển hai ngày đầu của Bờm, hãy tính toán mực nước biển ngày thứ \(N\).

Input

• Dòng 1: chứa 2 số nguyên \(b, a\) là mực nước biển 2 ngày đầu (\(-100 \le a, b \le 100\)). Số \(a\) là mực nước ngày thứ nhất, số \(b\) là mực nước ngày thứ 2.
• Dòng 2: chứa số nguyên dương \(N\) (\(3\le N\le 10^{12}\)).

Output

• Mực nước biển ngày thứ \(N\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n\le 10^7\)
• Subtask \(2\) (\(50\%\) số điểm): \(10^7<n\le 10^{12}\)

Example

1 2
3

3

3 1
​3

-1