Nosaukums
Viltīgais sienāzis (vilsie)
Laika limits
0.10s
Atmiņas limits
64.0 MB
Grūtība
27%

Definīcija

Viltīgais sienāzis atrodas plaknē koordinātās (1, 1). Tas grib nokļūt punktā (N, N), un tam ir plāns.

Sienāzis izdara sekojošu procedūru:

  1. Sākumā izvēlas vienu naturālu skaitli K no 1 līdz 2N.
  2. Veic vairākus lēcienus, līdz nonāk rūtiņā (NN). Vienā lēcienā sienāzis var nokļūt no rūtiņas (x, y) uz jebkuru rūtiņu (x + a, y + b), kur a, b ir veseli nenegatīvi skaitļi, un a + b = K.

Līdz ar to sienāža lēcieni definē punktu virkni, ko sauksim par ceļu.

Plaknes punkti ir vai nu brīvi (kur sienāzis var lekt), vai nu aizņemti (tur sēž vārdes, kas sienāzi apēd, tāpēc sienāzis tur nevar lekt).

Šajā uzdevumā jums ir jāsaskaita, cik dažādos ceļos sienāzis var nokļūt galapunktā. Divi ceļi ir atšķirīgi, ja atšķiras kaut viens no punktiem ceļos. Tā kā atbilde var būt liela, izvadiet to atlikumu, dalot ar 109+7.

Piemēram, sekojošā zīmējumā parādīti trīs dažādi ceļi, kad N = 6. Punktos ar vārdēm lekt nedrīkst.


Ievaddatu raksturojums

Pirmajā rindā dots viens skaitlis N, laukuma malas garums (2 ≤ N ≤ 1000). Nākamajās N rindās katrā doti pa N simboliem '.' vai '@', kas nozīmē, ka punkts ir brīvs, vai tajā ir vārde, attiecīgi. Garantēts, ka rūtiņas (1, 1) un (N, N) ir brīvas.

Ievērojiet, ka X koordināte pieaug labajā virzienā, bet Y koordināte pieaug uz augšu! Līdz ar to punkts (1, 1) atrodas kreisajā apakšējā stūrī, bet punkts (N, N) atrodas labajā augšējā stūrī.


Izvaddatu raksturojums

Izvadiet vienu skaitli, dažādu ceļu skaitu pēc moduļa 109+7.


Piezīmes

Apakšuzdevuma apraksts Punktu skaits
N ≤ 100 40
Bez papildus ierobežojumiem 60

Kopā:   

100


Paraugdati

Stdin
7
.......
.@..@..
.......
...@...
.@....@
.......
....@..
Stdout
274

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.