Bài tập

Hôm nay là ngày đầu tiên đi học của Sơn, ở trường cô giáo dạy cho Sơn về các phép toán cộng trừ giữa các con số. Một kiến thức mới khiến Sơn cảm thấy rất hào hứng đó là phép toán tính khoảng cách hai số. Khoảng cách 2 số được xác định bằng tổng chênh lệch giữa các chữ số tương ứng của 2 số đó. Nếu 1 số có số lượng chữ số ít hơn số còn lại thì ta xem như thêm các số \(0\) ở phía trước.

Ví dụ:

• Khoảng cách hai số \(4561\) và \(3278\) bằng \(|4 - 3| + |5 - 2| + |6 - 7| + |1 - 8| = 12\).
• Khoảng cách hai số \(32\) và \(5678\) bằng \(|0 - 5| + |0 - 6| + |3 - 7| + |2 - 8| = 21\).

Bố của Sơn muốn kiểm tra xem con mình có khả năng tính toán siêu cấp hay không nên đã đưa ra một vấn đề liên quan đến phép toán khoảng cách hai số. Cho hai số nguyên dương \(L, R\) hãy tính tổng khoảng cách của tất cả cặp số \((A, B)\) thỏa mãn \(L \leq A \ne B \leq R\). Tuy là một người ra đề bài nhưng bố Sơn cũng không biết kết quả là bao nhiêu, vì vậy nhờ bạn hãy tính toán kết quả chia lấy dư cho \(10^9 + 7\) của bài toán trên và gửi lại cho bố Sơn.

Input

• Một dòng duy nhất gồm \(2\) số nguyên dương \(L, R\) (\(L \leq R \leq 10^{50000}\)).

Output

• In ra số nguyên là kết quả bài toán chia lấy dư cho \(10^9 + 7\).

Example

288 291

76

Scoring

• Subtask 1 (25%): \(L, R \leq 10000\).
• Subtask 2 (30%): \(L, R \leq 10^{100}\).
• Subtask 3 (45%): Không có giới hạn gì thêm.

Bạn đang tham gia một trò chơi gồm \(n\) cấp độ. Mỗi cấp độ có một con quỷ trấn giữ. Ở các cấp độ từ \(1\) đến \(n-1\), bạn có thể chọn một trong hai hành động: tiêu diệt con quỷ hoặc bỏ qua và trốn thoát. Tuy nhiên, ở cấp độ thứ \(n\), bạn bắt buộc phải tiêu diệt con quỷ cuối cùng để giành chiến thắng.

Việc tiêu diệt một con quỷ sẽ tốn một khoảng thời gian là \(s \cdot f\), trong đó \(s\) là sức mạnh của con quỷ và \(f\) là hệ số kỹ năng hiện tại của bạn. Sau khi tiêu diệt một con quỷ, bạn sẽ nhận được một hệ số kỹ năng mới. Mục tiêu của bạn là tìm ra chiến lược chơi tối ưu để chiến thắng trò chơi với tổng thời gian nhỏ nhất có thể.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(x\) (\(1 \le n \le 2 \cdot 10^5\), \(1 \le x \le 10^6\)), lần lượt là số lượng cấp độ và hệ số kỹ năng ban đầu của bạn.
• Dòng thứ hai chứa \(n\) số nguyên \(s_1, s_2, \dots, s_n\) (\(1 \le s_1 \le s_2 \le \dots \le s_n \le 10^6\)), là sức mạnh của từng con quỷ.
• Dòng thứ ba chứa \(n\) số nguyên \(f_1, f_2, \dots, f_n\) (\(x \ge f_1 \ge f_2 \ge \dots \ge f_n \ge 1\)), là hệ số kỹ năng mới mà bạn sẽ nhận được sau khi tiêu diệt con quỷ ở cấp độ tương ứng.

Output

In ra một số nguyên duy nhất là tổng thời gian tối thiểu để chiến thắng trò chơi.

Example

5 100
20 30 30 50 90
90 60 20 20 10

4800

Cho một bảng số \(a\) nguyên kích thước \(m\cdot n\) và số nguyên \(k\). Hãy đếm xem trong dãy có bao nhiêu phần tử có giá trị \(k\).

Input

• Dòng 1: Gồm 2 số nguyên dương \(m, n\) và số nguyên \(k\).

• \(m\) dòng tiếp theo, mỗi dòng gồm \(n\) số

Output

• Kết quả bài toán

Example

2 3 4
2 4 6
6 4 2

2

Anh An là nhân viên kỹ thuật trong nhà máy X trên địa bàn tỉnh. Nhà máy được trang
bị dây chuyền sản xuất hiện đại, tất cả các sản phẩm khi đi qua băng chuyền được máy tính
đánh mã loại và lưu lại. Sản phẩm thứ i đi qua băng chuyền được gán bởi một số nguyên
đương \(a_{i}\) là mã loại tương ứng (các sản phẩm giống nhau thì có cùng một mã loại). Trong
một công đoạn sản xuất, có \(n\) sản phẩm đi qua băng chuyền được máy tính đánh mã loại và
lưu lại thành một dãy \(A\) gồm các số nguyên dương \(a_{1}, a_{2}, ...,a_n\). Kết thúc công đoạn, lãnh
đạo công ty yêu cầu anh An báo cáo số lượng tất cả các dãy con của dãy \(A\) thỏa mãn có ít
nhất \(k\) sản phẩm cùng mã loại \((1 \leq k \leq n)\), với dãy con là dãy được tạo từ các phần tử liên
tiếp của dãy \(A\).

Bạn hãy viết chương trình giúp anh An giải quyết bài toán trên.

Yêu cầu: Đưa ra số lượng tất cả các dãy con của dãy \(A\) có ít nhất \(k\) sản phẩm cùng mã loại.

Input

Từ tệp văn bản TKSP.INP gồm:

• Dòng đầu tiên chứa \(2\) số nguyên dương \(n, k\) \((1 \leq k \leq n \leq 4 \times 10^5)\)
• Dòng thứ \(2\) chứa \(n\) số nguyên dương \(a_1, a_2, ...,a_n (1 \leq a \leq 10^6)\)

Các số trên một dòng cách nhau bởi một dấu cách trống.

Output

Ghi ra tệp văn bản TKSP.OUT gồm một dòng chứa một số nguyên dương
thỏa mãn yêu câu bài toán.

Example

5 2
1 2 1 2 1

6

Scoring

• \(40\%\) số test với \(1 \leq n \leq 10^3\)
• \(40\%\) số test với \(10^3 < n \leq 10^4\)
• \(20\%\) số test với \(10^4 < n \leq 4 \times 10^5\)