დროის ლიმიტი: 1 წმ
მეხსიერების ლიმიტი: 64 მეგაბაიტი
შემავალი მონაცემები: stdin
გამომავალი მონაცემები: stdout
წყარო: USACO, 2005/06, MAR, BRONZE
ბეტსი ჩვეულებრივ ბალახობს მინდვრის ერთ ნაკვეთში, კოორდინანტებით R ხაზით (1 <= R <= 20) და C სვეტით (1 <= C <= 30). მინდორში
არის ბალახიანი (აღნიშნული '.'-ით) და ქვიანი(აღნიშნული 'R' -ით) ადგილები. ადგილი (1,1) არის ბადის ზედა მარცხენა კუთხე.
მზის ჩასვლისას ბეტსი უნდა დაბრუნდეს ბეღელში, რომელიც არის ბეტსიდან სამხრეთით და აღმოსავლეთით.
ბეტსის უნდა ბეღელში ყოველ საღამოს დაბრუნდეს ახალ-ახალი გზით. მას არ შეუძლია გაიაროს ქვიანი ადგილები. იგი მოძრაობს მხოლოდ
სამხრეთით (იზრდება ხაზის ნომერი) და აღმოსავლეთით (იზრდება სვეტის ნომერი)და არასოდეს ჩრდილოეთით ან დასავლეთით. გამოთვალეთ
რამდენ საღამოს შეუძლია აირჩიოს მან გზა, რომელზეც ჯერ არ გაუვლია.
მაგალითისთვის განვიხილოთ შემდეგი განლაგება:
B . . . B = ბეტსი . = გავლადი ადგილი R . . . R = ქვიანი . . . B B = ბეღელი
აქ არის 6 გზა, რომლის არჩევაც ბეტსის შეუძლია:
B## . . B## . . B#### . B## . . B###### B#### . R # . . R ### . R . # . R ##### R . . # R . ### . ####B . . ##B . . ##B . . . B . . . B . . . B შეტანის ფორმატი: * სტრიქონი 1: ორი ჰარით გამოყოფილი მთელი: R და C * სტრიქონები 2..R+1: ხაზი i+1 არის მინდვრის i-ური ხაზი და შეიცავს C რაოდენობის ჰარით გამოყოფილ ელემენტს, ყოველთაგან თითოეული
არის 'B', 'R', ან '.' . პირობიდან გამომდინარე ცხადია, რომ ორჯერ მოცემული 'B' არაა ორაზროვანი. გამოტანის ფორმატი: * სტრიქონი 1: ერთი მთელი - შესაძლო გზების რაოდენობა. პასუხი არ აჭარბებს 2,000,000,000-ს.
შესატანი მონაცემები
3 4 B . . . R . . . . . . B დაკოპირება
გამოსატანი მონაცემები
6 დაკოპირება