Annettuna on $n \times n$ -ruudukko, jonka jokaisessa ruudussa on kokonaisluku väliltä $1 \dots n^2$.

Ruudukossa oleva reitti alkaa jostain ruudusta ja siirtyy aina pysty- tai vaakasuunnassa toiseen ruutuun, jossa on pienempi luku kuin nykyisessä ruudussa. Ruutujen ei tarvitse olla vierekkäisiä, ja reitissä voi olla myös vain yksi ruutu.

Montako erilaista reittiä ruudukossa on? Koska vastaus voi olla suuri, ilmoita se modulo $10^9+7$ eli vastauksen jakojäännös luvulla $10^9+7$.

Syöte

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

Tämän jälkeen on $n$ riviä, joista jokaisella on $n$ lukua: ruudukon sisältö.

Tuloste

Tulosta yksi kokonaisluku: reittien määrä modulo $10^9+7$.

Esimerkki

Syöte:

3
2 1 3
1 1 1
9 2 7

Tuloste:

46

Selitys: Tässä esimerkissä mahdollisia ovat mm. seuraavat kolme reittiä:

Osatehtävä 1 (28 pistettä)

• $1 \le n \le 3$

Osatehtävä 2 (33 pistettä)

• $1 \le n \le 100$

Osatehtävä 3 (39 pistettä)

• $1 \le n \le 1000$