Đề 5 - Ngày 12/10/2026

Một mảnh vườn hình chữ nhật có chiều dài và chiều rộng là \(a\) và \(b\). Người ta làm hai lối đi vào khu vườn, mỗi lối song song với một chiều của hình chữ nhật với độ rộng của cả hai lối đi đều bằng \(c\).

Yêu cầu: Cho các giá trị \(a, b, c\). Hãy tính tổng diện tích phần còn lại của hình chữ nhật (phần trắng).

Input

• Nhập từ bàn phím ba số nguyên dương \(a, b, c\) (\(1 \le a, b \le 10^9, 1 \le c < \min(a, b)\)) cách nhau bằng dấu trống (space).

Output

• In ra màn hình một số nguyên là diện tích phần còn lại tìm được.

Example

4 5 1

12

Để chuẩn bị kỷ niệm ngày Nhà giáo Việt Nam (20/11), Đoàn trường có tổ chức giải chạy marathon cho học sinh trong toàn trường. Giải chạy có \(n\) học sinh tham gia. Kết quả xếp hạng theo thành tích từ cao xuống thấp và được đánh số từ \(1\) đến \(n\). Ban tổ chức trao thưởng cho học sinh tham gia như sau: Bạn xếp thứ \(n\) được \(1\) phần quà, các bạn còn lại sẽ nhận được số phần quà theo quy tắc: bạn xếp thứ \(i\) có số phần quà nhiều hơn bạn xếp thứ \(i + 1\) là \(a\).

Hãy cho biết Ban tổ chức cần chuẩn bị bao nhiêu phần quà để trao thưởng?

Input

• Nhập từ bàn phím hai số nguyên dương \(n\) và \(a\) (\(n \le 10^9, a \le 5\)) cách nhau bằng dấu trống (space).

Output

• In ra màn hình một số nguyên là số phần quà mà Ban tổ chức cần chuẩn bị.

Example

5 3

35

Công ty X chuyên sản xuất các sản phẩm theo dây chuyền. Các sản phẩm khi đưa lên băng chuyền để hoàn thiện các công đoạn cuối sẽ được gắn một mã hàng để quản lý. Mã hàng của mỗi sản phẩm là một số tự nhiên chính là thứ tự của sản phẩm đó khi đưa lên băng chuyền (\(1, 2, 3, \dots\)).

Do chưa kịp bảo dưỡng nên có hai công đoạn trên băng chuyền này không đảm bảo kỹ thuật. Trong đó, công đoạn thứ nhất cứ thực hiện trên \(a\) sản phẩm lại có một sản phẩm bị lỗi; công đoạn thứ hai cứ thực hiện trên \(b\) sản phẩm lại có một sản phẩm bị lỗi. Vì vậy, những sản phẩm có mã hàng chia hết cho \(a\) hoặc chia hết cho \(b\) đều bị lỗi nên hệ thống tự động loại ra các sản phẩm đó. Trong quá trình làm việc, nhân viên trực ca muốn biết mã hàng của sản phẩm hoàn thiện đảm bảo chất lượng thứ \(N\) là bao nhiêu để theo dõi, giám sát.

Yêu cầu: Em hãy viết chương trình tìm mã hàng của sản phẩm hoàn thiện thứ \(N\) giúp nhân viên trực ca.

Input

• Nhập từ bàn phím ba số nguyên dương \(a, b, N\) cách nhau bởi dấu cách (\(2 \le a, b \le 10^9; 2 \le N \le 10^{18}\)).

Output

• Ghi ra màn hình một số nguyên duy nhất chứa mã số của sản phẩm thứ \(N\) cần tìm.

Example

2 5 10

23

Scoring

• Subtask \(1\) (\(70\%\) số điểm): \(2 \le N \le 10^6\).
• Subtask \(2\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Cho dãy số nguyên dương \(a_1, a_2, \dots, a_n\). Một bộ ba là bộ gồm ba số nguyên \(a_i, a_j, a_k\) với \(1 \le i < j < k \le n\). Giá trị của bộ ba này được tính bằng tích \(a_i \cdot a_j \cdot a_k\).

Yêu cầu: Hãy tính tổng giá trị của tất cả các bộ ba khác nhau. Hai bộ ba \(a_i, a_j, a_k\) và \(a_u, a_v, a_w\) được gọi là khác nhau nếu \(i \neq u\) hoặc \(j \neq v\) hoặc \(k \neq w\). Do con số này có thể rất lớn nên bạn chỉ cần in phần dư của nó khi chia cho \(10^9 + 7\).

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(n \le 10^6\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) (\(a_i \le 10^5, \forall i\)) cách nhau bằng dấu trống (space).

Output

• Một số nguyên duy nhất là kết quả tìm được sau khi chia lấy dư cho \(10^9 + 7\).

Example

5
1 2 1 3 1

34

Scoring

• Có \(20\%\) số điểm ứng với \(n \le 100, a_i \le 10\);
• Có \(20\%\) số điểm ứng với \(500 < n \le 5000\);
• Có \(60\%\) số điểm không ràng buộc gì thêm.