Ruudukko

• Time limit: 1.00 s
• Memory limit: 128 MB

$7 \times 7$ -ruudukossa vasemmasta yläkulmasta vasempaan alakulmaan on 88418 erilaista reittiä. Jokaista reittiä vastaa 48-merkkinen kuvaus, joka muodostuu merkeistä A (alas), Y (ylös), V (vasen) ja O (oikea).

Esimerkiksi reittiä

vastaa kuvaus AOYOOOOOAAAVYYVAAAVAOOYOAAVVVVVYOYVYOOYYVAVVAAAA.

Sinulle on annettu kuvaus, jossa osa merkeistä on ? (mikä tahansa suunta). Tehtäväsi on laskea, montako reittiä vastaa kuvausta.

Syöte

Syötteenä on reitin kuvaava merkkijono, joka muodostuu merkeistä ?, A, Y, V ja O.

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: montako reittiä on olemassa.

Esimerkki

Syöte:
??????O??????Y??????????????????????????VA????A?

Tuloste:
201