Nhân ma trận

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/

Giờ học về phép chia có dư tỏ ra quá dễ dàng cho các bé trường mầm non SuperKids, để tăng tính hấp dẫn cho giờ học, cô giáo muốn đặt ra một thách thức mới.

Cho ba số nguyên dương \(x, n, m\). Cô giáo xét dãy chữ số là biểu diễn thập phân của \(x\) và viết lặp đi lặp lại dãy chữ số này \(n\) lần để được biểu diễn thập phân của một số \(y\). Nhiệm vụ của các bé là phải cho biết số dư của \(y\) khi chia cho \(m\).

Ví dụ với \(x = 12, n = 3, m = 8\). Số \(y = 121212\), số dư của \(y\) khi chia cho 8 là 4.

Các bé làm việc rất hào hứng và nhanh chóng đưa ra kết quả, vấn dề của cô giáo là cần biết kết quả đúng để phát phiếu bé ngoan cho các bé làm đúng và nhanh nhất. Em hãy giúp cô giáo tính toán kết quả.

Input

• Một dòng chứa 3 số guyên dương \(x, n, m. (x, n, m \le 10^{18})\)

Output

• Một số nguyên dương là số dư của y khi chia cho \(m\).

Example

12 3 8

4

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

Dãy Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng hai phần tử 0 và 1, các phần tử sau đó được thiết lập theo quy tắc mỗi phần tử luôn bằng tổng hai phần tử trước nó. Dãy số Fibonacci rất đặc biệt này được Leonardo Fibonacci (hay còn có tên tên khác là Leonarda da Pisa) là một nhà toán học người Ý công bố vào năm 1202 trong cuốn sách Liber Abacci - Sách về toán đố qua 2 bài toán: Bài toán con thỏ và bài toán số các "cụ tổ" của một ong đực.

Henry E Dudeney (1857 - 1930) (là một nhà văn và nhà toán học người Anh) nghiên cứu ở bò sữa, cũng đạt kết quả tương tự.

Thế kỉ XIX, nhà toán học Edouard Lucas (người Pháp) xuất bản một bộ sách bốn tập với chủ đề toán học giải trí, ông đã dùng tên Fibonacci để gọi dãy số kết quả của bài toán từ cuốn Liber Abaci – bài toán đã sinh ra dãy Fibonacci.

Dãy số này hầu như biến hóa vô tận. Chính đều đó làm cho bao nhà toán học (chuyên nghiệp lẫn nghiệp dư) và ngay cả chúng ta say mê nghiên cứu, khám phá về nó.

Xét dãy số \(fib3\) là một biến thể của dãy số Fibonacci, với ba số nguyên không âm \(a, b, c\) ta xây dựng dãy số theo quy tắc sau:
\(fib3(n) = \left\{ \begin{array}{cl} n & if\ n \le 3 \\ a.fib3(n-1)+b.fib3(n-2)+c.fib3(n-3) & if\ n\%3=1\\ b.fib3(n-1)+c.fib3(n-2)+a.fib3(n-3) & if\ n\%3=2\\ c.fib3(n-1)+a.fib3(n-2)+b.fib3(n-3) & if\ n\%3=3\\ \end{array} \right.\)
Yêu cầu: Cho 5 số nguyên không âm \(a, b, c, k, n\). Hãy tính số \(fib3(n)\%k\).

Input

• Nhiều dòng, mỗi dòng chứa 5 số nguyên không âm (\(a, b, c, k, n\)) (\(a, b, c, k≤10^9\)).

Output

• Mỗi dòng tương ứng của dữ liệu vào, in ra một số là kết quả tìm được tương ứng với dữ liệu vào.

Scoring

• Subtask 1: \(n≤10^6\) ;
• Subtask 2: \(n≤10^9, a=b=c=1\);
• Subtask 3: \(n≤10^9\).

Example

1 1 1 100 4    

6

1 1 1 111539786 1    

1

Nguồn: CĐ DHBB

Xét dãy số Fibonacci \({Fn}\) theo định nghĩa:

• \(𝐹_0=𝐹_1=1\)
• \(𝐹_n=𝐹_{n-1}+𝐹_{n-2}\ ∀𝑛>1\)

Yêu cầu: Cho số \(𝒏\), hãy tính tổng \(𝑆=𝐹_0+𝐹_1+𝐹_2+⋯+𝐹_𝑛\) và đưa ra số dư của \(S\) chia cho (\(10^9+7\)).

Input

• Chỉ một dòng duy nhất ghi số nguyên dương \(n\) (\(𝑛≤10^{15}\)).

Output

• Ghi một số nguyên \(S\) – số dư tìm được.

Example

3    

7

5    

20

Nguồn: CĐ DHBB

Cho một tứ diện, đánh dấu các đỉnh lần lượt là \(A, B, C, D\).

Một con kiến ​​đang đứng trên đỉnh \(D\) của tứ diện. Con kiến ​​khá tích cực di chuyển và nó không chịu nhàn rỗi. Với mỗi bước đi, nó bước từ một đỉnh tới đỉnh khác dọc theo một số cạnh của tứ diện. Con kiến ​​không bao giờ chịu đứng yên ở một chỗ.

Yêu cầu: Đếm số cách mà con kiến ​​có thể đi từ đỉnh \(D\) ban đầu rồi quay về chính nó trong đúng \(n\) bước. Nói cách khác, bạn sẽ được yêu cầu tìm ra số con đường tuần hoàn khác nhau có chiều dài \(n\) từ đỉnh \(D\) đến chính nó. Vì số có thể khá lớn nên bạn nên in theo \(modulo (10^9 + 7)\).

Input

• Dòng đầu tiên chứa số nguyên duy nhất \(n (1 \le n \le 10^7)\) - chiều dài của đường đi.

Output

• In số nguyên duy nhất là kết quả tìm được \(modulo (10^9+ 7)\).

Scoring

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

Example

2

3