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