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ņā (N, N). 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 10⁹+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.

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ī.

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