THTA TP ĐN 2024 & Thi thử HSG9 Lần 1

Lũy thừa \(a^n\) (đọc là \(a\) mũ \(n\)) là tích của \(n\) thừa số \(a\). Ký hiệu \(a^n = a \times a \times \dots \times a\) (\(n\) thừa số \(a\)). Quy ước: \(a^0 = 1\).

Ví dụ: \(2^4 = 2 \times 2 \times 2 \times 2\).

Nam rất thích các bài toán về lũy thừa. Trong ngày kỷ niệm 49 năm giải phóng thành phố Đà Nẵng 29/3/1975 - 29/3/2024, Nam đố Mai một bài toán sau: "Cho một số tự nhiên \(n\), in ra chữ số cuối của phép lũy thừa \(2903^n\)".

Bạn là người giỏi lập trình, hãy giúp Mai giải bài toán này nhé!

Input

• Nhập từ bàn phím số nguyên \(n\) (\(n < 10^{10}\)).

Output

• In ra màn hình kết quả của bài toán là chữ số cuối của giá trị \(2903^n\).

Example

1

3

2

9

Cho xâu \(S_1\) là xâu con của một xâu \(S_2\) nếu \(S_1\) là một chuỗi các ký tự liên tiếp của \(S_2\).
Ví dụ: bc là xâu con của abcd.

Yêu cầu: Đọc hai xâu \(S_1, S_2\). Nếu xâu \(S_1\) là xâu con của xâu \(S_2\) thì in ra vị trí xuất hiện cuối cùng của xâu \(S_1\) trong \(S_2\). Nếu xâu \(S_1\) không phải là xâu con của xâu \(S_2\) thì ghi ra số \(0\).

Input

• Nhập từ bàn phím 2 dòng: dòng thứ nhất ghi xâu \(S_1\), dòng thứ hai ghi xâu \(S_2\).

Output

• In ra màn hình vị trí xuất hiện cuối cùng của xâu con, hoặc \(0\) nếu không thỏa mãn.

Example

abc
abcabcbc

4

ababab
babsbabbb

0

Cho bảng hình vuông kích thước \(N \times N\). Người ta điền \(N \times N\) số đầu tiên của dãy \(1, 3, 5, \dots\) vào bảng theo hình xoắn ốc từ ngoài vào trong, theo chiều kim đồng hồ bắt đầu từ ô góc trái bên trên.

Hình minh họa chính thức cho bảng \(4 \times 4\) và \(5 \times 5\):

Input

• Nhập từ bàn phím một số nguyên dương \(N\) (\(1 \le N \le 10000\)).

Output

• In ra màn hình một số nguyên dương là tổng các số lớn nhất trên mỗi dòng của bảng.

Example

4

84

5

165

Cho một xâu kí tự \(s\) chỉ gồm các kí tự trong bảng mã ASCII. Ta gọi một phép dịch xâu \(s\) qua \(k\) kí tự là chuyển \(k\) kí tự ở cuối của xâu \(s\) lên đầu.

Ví dụ: \(s\) = abbaac, \(k = 3\) thì xâu \(s\) trở thành aacabb.

Yêu cầu: Cho xâu \(s\) và một số nguyên dương \(k\). In ra xâu \(s\) sau khi dịch qua \(k\) kí tự.

Input

• Dòng đầu gồm xâu \(s\).
• Dòng thứ hai gồm số nguyên dương \(k\).
• Dữ liệu đảm bảo \(1 \le k \le |s| \le 300\), với \(|s|\) là độ dài xâu \(s\).

Output

• Một dòng duy nhất là xâu \(s\) sau khi dịch qua \(k\) kí tự.

Example

Npndqtldcphktnh
5

hktnhNpndqtldcp

Scoring

• \(60\%\) số điểm có \(1 \le k \le |s| \le 50\) và xâu \(s\) chỉ gồm các kí tự in thường a, b, c, d, ..., z.
• \(40\%\) số điểm còn lại không có ràng buộc gì thêm.

Cho dãy số \(f_1, f_2, f_3, f_4, f_5, \dots\) được định nghĩa như sau:

• \(f_1 = 2\)
• \(f_i = f_{i-1} + i \cdot (i + 1)\)

Yêu cầu: Tính \(f_n\).

Input

• Một dòng duy nhất gồm số nguyên dương \(n\) (\(n \leq 10^9\)).

Output

• Một dòng duy nhất là giá trị của \(f_n\) sau khi chia lấy dư cho \(10^9 + 7\).

Example

4

40

Scoring

• \(40\%\) số điểm có \(n \leq 10^3\).
• \(40\%\) số điểm có \(n \leq 10^6\).
• \(20\%\) số điểm còn lại không có ràng buộc gì thêm.