Sinulle annetaan n \times n -ruudukko, jonka rivit ja sarakkeet on numeroitu 1,2,\dots,n. Ruudukon rivillä y sarakkeessa x on kokonaisluku a[y][x].

Tehtäväsi on laskea yhteen ruudukon kaikkien aliruudukoiden lukujen summat. Jokainen aliruudukko sisältää luvut suorakulmaiselta alueelta, jonka vasen yläkulma on kohdassa (y_1,x_1) ja oikea alakulma on kohdassa (y_2,x_2). Tällaisen aliruudukon lukujen summa on \sum_{y=y_1}^{y_2} \sum_{x=x_1}^{x_2} a[y][x].

Syöte

Ensimmäisellä rivillä on kokonaisluku n: ruudukon koko.

Seuraavat n riviä kuvaavat ruudukon. Jokaisella rivillä on n kokonaislukua.

Kaikissa testeissä 1 \le a[y][x] \le 10^6.

Tuloste

Tulosta yksi kokonaisluku: haluttu vastaus modulo 10^9+7.

Esimerkki

Syöte:

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

Tuloste:

1136

Osatehtävä 1 (13 pistettä)

• 1 \le n \le 10

Osatehtävä 2 (36 pistettä)

• 1 \le n \le 100

Osatehtävä 3 (51 pistettä)

• 1 \le n \le 1000