Cho 1 dãy số nguyên dương, tuân theo quy luật sau:

• ~1~ phần tử đầu tiên có giá trị là ~1~.
• ~2~ phần tử tiếp theo có giá trị là ~2~.
• ~3~ phần tử tiếp theo có giá trị là ~3~.
• ~\dots~
• ~m~ phần tử tiếp theo có giá trị là ~m~.

Nói cách khác, dãy số sẽ có dạng ~1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5,\dots~

Cho một số nguyên dương ~n~, hãy tính tổng của ~n~ phần tử đầu tiên trong dãy số trên.

Vì kết quả có thể rất lớn nên hãy lấy kết quả chia dư cho ~10^9+7~.

Dữ liệu vào:

• Dòng đầu tiên chứa một số nguyên dương ~t\ (t\leq 10)~.
• ~t~ dòng tiếp theo, mỗi dòng chứa duy nhất một số nguyên dương ~n\ (n \leq 10^{18})~.

Dữ liệu ra:

• In ra ~t~ dòng, mỗi dòng là tổng của ~n~ số đầu tiên trong đãy, sau khi chia dư cho ~10^9+7~.

Input:

2
3
6

Output:

5
14

Giới hạn:

• Có ~40\%~ số test ứng với ~40\%~ số điểm của bài có ~n\leq 10^6~.
• Có ~60\%~ số test còn lại ứng với ~60\%~ số điểm của bài không có ràng buộc gì thêm.

Nate vừa mua được một mảnh đất ở thành phố ABC để xây nhà.

Khu đất của Nate có kích thước ~M \times N~ mét vuông (~m^2~). Cậu muốn xây một ngôi nhà có dạng hình vuông có chiều dài là số nguyên dương có diện tích lớn nhất có thể và nằm hoàn toàn trong khu đất mà Nate đã mua. Tuy nhiên, để xây được một ngôi nhà an toàn, phần đất được chọn phải đạt được một số tiêu chí nhất định.

Nate đã tiến hành một cuộc khảo sát trên mảnh đất bằng cách chia mảnh đất thành các ô vuông nhỏ, mỗi ô có diện tích ~1 \times 1~ ~(m^2)~ và đưa ra số liệu về độ nguy hiểm của mỗi ô trên mảnh đất này. Độ nguy hiểm của ô ở hàng thứ ~i~, cột thứ ~j~ của mảnh đất là ~A_{(i,\ j)}~. Để một mảnh đất có kích thước ~X \times X~ ~(m^2)~ đạt tiêu chuẩn xây nhà, tổng độ nguy hiểm của tất cả các ô trong mảnh đất phải không vượt quá ~K~. Nói cách khác, một mảnh đất có kích thước ~X \times X~ ~(m^2)~ có góc trên bên trái là ô ~A_{(x,\ y)}~ và góc dưới bên phải là ô ~A_{(x+X-1,\ y+X-1)}~ (~1 \leq x \leq m; 1 \leq y \leq n~) đạt tiêu chuẩn xây nhà khi và chỉ khi điều kiện sau thỏa mãn:

$$\sum_{i=x}^{x+X-1} \sum_{j=y}^{y+X-1} a_{(i,\ j)} \leq k$$

Mảnh đất của Nate mua rất lớn nên cậu nhờ bạn giúp. Hãy tìm chiều dài nhà ~X~ lớn nhất mà tồn tại một mảnh đất trong khu đất đã mua của Nate có thể xây nhà chiều dài ~X.~ Nếu không tồn tại bất kỳ mảnh đất với bất kỳ kích thước nào có thể xây nhà, in ra 0.

Dữ liệu vào:

• Dòng đầu tiên gồm ba số nguyên dương ~M, N, K~ (~1 \leq M, N \leq 2000~; ~K \leq 10^9~) lần lượt là chiều rộng, chiều dài của khu đất và độ nguy hiểm tối đa mà ngôi nhà có thể có.
• ~M~ dòng tiếp theo, dòng thứ ~i~ gồm ~N~ số nguyên không âm ~A_{(i,1)}, A_{(i,2)}, \ldots, A_{(i,N)}~ là độ an toàn của từng ô của khu đất (~0 \leq A_{(i,j)} \leq 10^9~).

Dữ liệu ra:

• Một số nguyên ~X~ là đáp án của bài toán.

Input:

5 5 2
1 0 0 3 2
0 0 0 1 0
0 0 1 2 3
3 2 1 0 1
0 0 1 2 1

Output:

3

Giới hạn:

• Có ~50\%~ số test ứng với ~50\%~ số điểm của bài có ~m,n \leq 500~.
• Có ~50\%~ số test còn lại ứng với ~50\%~ số điểm của bài không có ràng buộc gì thêm.

Cho một ma trận các số nguyên có kích thước ~N\times N~. Lúc đầu chúng ta đứng tại ô tọa độ ~(1,1)~.

Chúng ta có thể di chuyển xuống dưới hoặc sang phải. Điều này có nghĩa là nếu chúng ta đứng ở ô ~(i, j)~ thì có thể di chuyển đến ô ~(i + 1, j)~ hoặc ~(i, j + 1)~.

Mặt khác chúng ta được phép di chuyển tối đa ~K~ bước sang trái hoặc lên trên. Có nghĩa là nếu chúng ta đứng ở ô ~(i, j)~ thì có thể di chuyển đến ô ~(i, j - 1)~ hoặc ~(i - 1, j)~.

Chúng ta không thể di chuyển ra ngoài ma trận. Khi chúng ta di chuyển tới một ô (bao gồm cả ô xuất phát ~(1, 1)~), chúng ta cộng số nguyên trong ô này vào tổng. Nếu chúng ta đi vào một ô nhiều hơn một lần thì mỗi lần đi vào chúng ta lại cộng số nguyên ở ô này vào tổng. Ban đầu tổng bằng ~0~.

Bạn hãy viết một chương trình tính tổng lớn nhất có thể, bắt đầu từ ô ~(1, 1)~ và kết thúc ở ô ~(N, N)~ với các bước di chuyển được mô tả như ở trên.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~K\ (2\leq N\leq 1000; 0\leq K\leq 100)~.
• Tiếp theo có ~N~ dòng, mỗi dòng chứa ~N~ số nguyên có giá trị thuộc đoạn ~[-1000;1000]~ là các phần tử của ma trận đã cho.

Dữ liệu ra:

• Gồm một dòng chứa tổng lớn nhất của việc di chuyển bắt đầu từ ô ~(1, 1)~ và kết thúc ở ô ~(N, N)~ với các bước di chuyển được mô tả như ở trên.

Input 1:

3 1
1 1 0
1 1 0
1 1 1

Output 1:

7

Input 2:

4 4
1 1 1 0
1 0 1 0
1 1 1 0
0 0 1 1

Output 2:

15

Giới hạn:

• Có ~33\%~ số test ứng với ~33\%~ số điểm của bài có ~n, k\leq 10~.
• Có ~66\%~ số test còn lại ứng với ~66\%~ số điểm của bài không có ràng buộc gì thêm.

Bài giảng về quy hoạch động được minh họa bằng bài toán tìm đường đi trên lưới ô vuông như sau.

Cho lưới ô vuông hình chữ nhật có ~m~ dòng và ~n~ cột. Mỗi ô ~(i, j)~ của lưới có ghi một số nguyên ~a_{ij}\ (i = 1, 2,\dots,m;\ j = 1, 2,\dots, n)~. Từ mỗi ô chỉ có thể di chuyển sang ô kề cạnh bên phải hoặc xuống dưới (nếu tồn tại ô đến). Giá trị đường đi là tổng các số ghi trên những ô nằm trên đường đi. Hãy tìm đường đi có giá trị lớn nhất, xuất phát từ ô trên trái và kết thúc ở ô dưới phải. Đường đi này được gọi là đường đi tối ưu.

Bài giảng trên được mở rộng và nâng cao ở buổi ngoại khóa cho học sinh giỏi. Một loạt các test được tạo ra để kiểm tra chương trình của học sinh. Xây dựng test mới là một việc khó và buồn tẻ. Vì vậy thầy giáo thông báo là sử dụng các test cũ đã có, nhưng ở mỗi test giá trị một ô bị thay đổi thành số cực nhỏ (có thể bằng ~0~ hoặc âm) để đường đi tối ưu không còn được như cũ và giá trị đường đi tối ưu mới sẽ là nhỏ nhất trong số các khả năng giá trị một ô bị thay đổi. Ô trên trái và ô dưới phải vẫn giữ nguyên giá trị cũ. Hình vẽ sau minh họa cho ví dụ ở dưới.

Yêu cầu: Cho test ban đầu, hãy xác định giá trị của đường đi tối ưu mới sau khi thay đổi giá trị ở một ô theo điều kiện đã nêu.

Dữ liệu vào:

• Dòng đầu tiên chứa 2 số nguyên ~m~ và ~n\ (2\leq m, n\leq 1500)~.
• Dòng thứ ~i~ trong ~m~ dòng sau chứa ~n~ số nguyên ~a_{i1},a_{i2},\dots ,a_{in}\ (1\leq a_{ij}\leq 10^9)~.

Dữ liệu ra:

• Ghi ra một số nguyên dương duy nhất là giá trị đường đi tối ưu mới.

Input:

4 4
1 2 3 4
2 1 3 1
3 2 3 5
1 3 4 1

Output:

17

Giới hạn:

• Có ~60\%~ số test ứng với ~60\%~ số điểm của bài có ~2\leq m, n\leq 50~.
• Có ~20\%~ số test ứng với ~20\%~ số điểm của bài có ~2\leq m, n\leq 300~.
• Có ~20\%~ số test còn lại ứng với ~20\%~ số điểm của bài không có ràng buộc gì thêm.