Cho ~N~ dãy số không giảm ~A_1, A_2, \dots, A_N~, 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 ~A_i~ và ~A_j~ (~1 \le i, j \le N~), ta gọi dãy gộp (ký hiệu là ~A_{ij}~) của hai dãy ~A_i, A_j~ là dãy gồm tất cả ~2L~ phần tử của hai dãy ~A_i, A_j~ đượ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ó.

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 ~A_{ij}~ với ~1 \le i < j \le N~.

Input

• Dòng đầu tiên chứa hai số ~N~ và ~L~ (~2 \le N \le 200, 1 \le L \le 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~. Các phần tử có trị tuyệt đối không vượt quá ~10^9~.

Output

• Ghi ra giá trị ~t \pmod{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 ~A_{ij}~ với ~1 \le i < j \le N~.

Sample Input 1

3 6
1 2 3 4 5 6
3 4 5 6 7 8
0 0 1 1 2 2

Sample Output 1

8