Cho dãy số có quy luật như sau: \(1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, ...\)

Yêu cầu: Cho số nguyên dương \(n\), hãy tính tổng \(n\) số đầu tiên của dãy.

Input

• Gồm một dòng chứa số nguyên dương \(n\).

Output

• Ghi ra một số nguyên là tổng \(n\) số đầu tiên của dãy chia dư cho \(10^9 + 7\).

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \le 10^6\).
• Subtask \(2\) (\(50\%\) số điểm): \(n \le 10^{18}\).

Example

5

11

Có \(n + 1\) đội bóng, các đội được đánh số từ \(0\) đến \(n\). Đội bóng số \(0\) dự định tổ chức một giải giao hữu và mời \(n\) đội tham gia. Khi tham gia, đội thứ \(i\) \((1 \le i \le n)\) dự định thi đấu đúng \(s_i\) \((1 \le s_i \le n)\) trận. Gọi \(s_0\) là số trận mà đội số \(0\) sẽ thi đấu, dựa vào số liệu đăng kí của mỗi đội, đội số \(0\) muốn biết \(s_0\) có thể nhận những giá trị nào để có thể tổ chức giải đấu với số lượng trận đúng như các đội đã đăng kí mà mỗi cặp đội sẽ đấu với nhau không quá một trận.

Yêu cầu: Cho các số nguyên dương \(s_1, s_2, ..., s_n\), hãy đếm xem có bao nhiêu giá trị nguyên dương \(s_0\) thỏa mãn.

Input

• Dòng đầu chứa số nguyên dương \(n\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(s_1, s_2, \dots, s_n\).

Output

• Ghi ra một số nguyên là số lượng giá trị \(s_0\) thỏa mãn.

Scoring

• Subtask \(1\) (\(15\%\) số điểm): \(n \le 5\).
• Subtask \(2\) (\(15\%\) số điểm): \(n \le 50\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \le 500\).
• Subtask \(4\) (\(20\%\) số điểm): \(n \le 5000\).
• Subtask \(5\) (\(15\%\) số điểm): \(n \le 50000\).
• Subtask \(6\) (\(15\%\) số điểm): \(n \le 500000\).

Example

2
2 2

1

Trên một khoảng sân rộng có chiều dài \(L\), người ta đặt một số thùng hàng. Dưới đây là một hình ảnh về sân có chiều dài 10, có chứa 5 thùng hàng A, B, C, D, E.

Hoàng muốn di chuyển các thùng hàng để tạo ra một khoảng sân có độ rộng tối thiểu là \(W\) để có thể chơi bóng cùng các bạn của mình. Mỗi bước, Hoàng có thể di chuyển một thùng hàng sang trái hoặc sang phải nếu vị trí vẫn nằm trong sân và vị trí đó còn trống.
Với ví dụ trên, khi Hoàng cần một khoảng sân độ rộng tối thiểu là \(3\), thì dưới đây là một cách di chuyển các thùng hàng. Cách di chuyển này cần \(2\) bước di chuyển.

Nếu Hoàng cần một khoảng sân độ rộng tối thiểu là \(4\), thì dưới đây là một cách di chuyển các thùng hàng. Cách di chuyển này cần \(4\) bước di chuyển.

Nếu Hoàng cần một khoảng sân độ rộng tối thiểu là \(5\), thì dưới đây là một cách di chuyển các thùng
hàng. Cách di chuyển này cần \(7\) bước di chuyển.

Yêu cầu: Cho vị trí ban đầu của các thùng hàng và giá trị \(W\), bạn hãy giúp Hoàng tính số bước di chuyển ít nhất.

Input

• Dòng đầu tiên ghi số \(T\) là số bộ dữ liệu \((T \le 10)\)
• \(T\) dòng tiếp theo, mỗi dòng mô tả một bộ dữ liệu. Mỗi dòng chứa một xâu kí tự \(s\) mô tả sân có độ dài không quá \(5 × 10^5\) và số nguyên dương \(W\) cách nhau bởi dấu cách. Xâu kí tự \(s\) chỉ gồm dấu chấm hoặc kí tự \(X\), trong đó kí tự chấm thể hiện vị trí sân không có thùng hàng và kí tự \(X\) thể hiện vị trí sân có thùng hàng.

Output

• Ghi ra \(T\) dòng, mỗi dòng chứa một số nguyên là ra số lần di chuyển các thùng hàng ít nhất.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): độ dài xâu \(s\) không vượt quá \(50\) và có không quá \(3\) thùng hàng.
• Subtask \(2\) (\(10\%\) số điểm): độ dài xâu \(s\) không vượt quá \(20\).
• Subtask \(3\) (\(10\%\) số điểm): độ dài xâu \(s\) không vượt quá \(50\).
• Subtask \(4\) (\(10\%\) số điểm): độ dài xâu \(s\) không vượt quá \(200\).
• Subtask \(5\) (\(25\%\) số điểm): độ dài xâu \(s\) không vượt quá \(5000\).
• Subtask \(6\) (\(20\%\) số điểm): độ dài xâu \(s\) không vượt quá \(50000\).
• Subtask \(7\) (\(15\%\) số điểm): không có ràng buộc gì thêm.

Example

4
.XX..XX.X. 2
.XX..XX.X. 3
.XX..XX.X. 4
.XX..XX.X. 5

0
2
4
7