7251번 - Puokštė 서브태스크다국어

Robotas yra pastate, turinčiame N aukštų. Kiekviename aukšte yra po M iš eilės įrengtų kambarių, išdėstytų iš eilės taip, kad visi pastato kambariai sudarytų N × M dydžio stačiakampį. Kai kuriuose kambariuose yra po gėlę. Robotas mokysis surinkti puokštes.

Kai robotas yra kuriame nors kambaryje, jis gali elgtis taip:

• Jei kambarys nėra pats kairiausias, jis gali pereiti į kairesnį kambarį tame pačiame aukšte.
• Jei kambarys nėra pats dešiniausias, jis gali pereiti į dešinesnį kambarį tame pačiame aukšte.
• Jei jis nėra apatiniame aukšte, jis gali persikelti į tiesiai po dabartiniu kambariu esantį kambarį vienu aukštu žemiau.

Robotas juda tik horizontaliai arba žemyn, bet niekada nekyla aukštyn.

Kai jis įeina į kambarį, kuriame yra gėlė, jis būtinai ją paima ir deda į puokštę.

Visos gėlės yra skirtingos, o taip pat puokštės išvaizda priklauso nuo to, kokia tvarka į ją dedamos gėlės. Dvi puokštės laikomos skirtingomis, jei jas sudaro skirtingos gėlės arba skiriasi gėlių įdėjimo į puokštę tvarka.

Robotas pradeda bet kuriame viršutinio aukšto kambaryje ir baigia bet kuriame apatinio aukšto kambaryje.

Be to, robotas visada pasirenka tokį maršrutą, kad kiekviename aukšte paimtų bent po vieną gėlę.

Nustatykite, kiek yra skirtingų variantų, kokią puokštę robotas gali būti surinkęs pabaigoje. Atsakymą išveskite moduliu 10⁹ + 7.

Pirmoje eilutėje pateikiami skaičiai N ir M.

Tolesnėse N eilučių (viena eilutė aprašo vieną aukštą, pradedant nuo viršutinio) yra po M raidžių, kurių i-oji nurodo, ar i-ajame to aukšto kambaryje iš kairės yra gėlė:

• O – kambaryje gėlės nėra
• X – kambaryje gėlė yra.

Garantuojama, kad kiekviename aukšte yra bent po vieną gėlę.

Išveskite, kiek yra skirtingų puokščių, kurias gali surinkti robotas, moduliu 10⁹ + 7.

• 1 ≤ N ≤ 500
• 1 ≤ M ≤ 300