Cho N dãy số không giảm A1, A2, ..., AN, mỗi dãy gồm L số nguyên (dãy số được gọi là không giảm nếu mỗi phần tử đứng sau là lớn hơn hoặc bằng phần tử đứng trước). Xét hai dãy Ai và Aj (1≤ i, j ≤ N), ta gọi dãy gộp (ký hiệu là Aij) của hai dãy Ai, Aj là dãy gồm tất cả 2L phần tử của hai dãy Ai, Aj được sắp xếp theo thứ tự không giảm và phần tử đứng ở vị trí thứ L trong dãy gộp được gọi là phần tử trung vị của nó.

Ví dụ: Xét hai dãy số

Ai = (1 3 4 5 6); Aj = (0 1 5 6 7).

Khi đó dãy gộp Aij từ hai dãy đã cho là: 0 1 1 3 4 5 5 6 6 7 có phần tử trung vị là 4.

Yêu cầu: Tính tổng của tất cả các phần tử trung vị của tất cả các dãy gộp Aij với 1≤ i < j ≤ N.

Dữ liệu: Vào từ file test.inp:

• Dòng đầu tiên chứa hai số N và L (2 ≤ N ≤ 200, 1 ≤ L ≤ 20000);
• Dòng thứ i trong số N dòng tiếp theo chứa L số nguyên là các phần tử của dãy thứ i trong số N dãy đã cho. Giả thiết là các phần tử của các dãy số là các số nguyên có trị tuyệt đối không vượt quá 10^9
• Hai số liên tiếp trên cùng một dòng trong file dữ liệu được ghi cách nhau bởi ít nhất một dấu cách.

Kết quả: Ghi ra file văn bản test.out giá trị t mod 10^9 (là phần dư trong phép chia t cho 10^9), trong đó t là tổng của tất cả các phần tử trung vị của tất cả các dãy gộp Aij với 1≤ i < j≤ N.