כפי שבני אדם אוהבים קלאס, הפרות של Farmer John המציאו גרסה משלהן. כשמשחקות חיות מגושמות שמשקלן כמעט טון, המשחק כמעט תמיד נגמר באסון, אך למרבה הפלא זה אינו מונע מהן לנסות כמעט בכל אחר צוהריים.
משחקים ברשת של $R$ שורות ו־$C$ עמודות ($2 \leq R \leq 15$, $2 \leq C \leq 15$), וכל משבצת אדומה או כחולה. הפרות קופצות מהפינה השמאלית העליונה לימנית התחתונה. קפיצה תקינה אם ורק אם:
- צבע משבצת היעד שונה;
- היא לפחות שורה אחת מתחת למשבצת הנוכחית; וגם
- היא לפחות עמודה אחת ימינה מהמשבצת הנוכחית.
ספרו את סדרות הקפיצות התקינות השונות מהפינה השמאלית העליונה לימנית התחתונה.
קלט
השורה הראשונה מכילה $R$ ו־$C$. $R$ השורות הבאות מכילות $C$ תווים כל אחת. כל תו הוא R או B, לאדום או כחול בהתאמה.
פלט
הדפיסו את מספר הדרכים השונות לקפוץ מהפינה השמאלית העליונה לימנית התחתונה.
דוגמאות
קלט 1
4 4 RRRR RRBR RBBR RRRR
פלט 1
3
מחבר הבעיה: Nick Wu, 2015