Walk and jump P87501


Statement
 

pdf   zip

thehtml

Given an n × m map with obstacles, in how many ways can we go from the upper-left corner to the lower-right corner? We can only walk (move to the cell immediately to the right or below), or jump (move to the cell two positions to the right or below, but only by jumping an obstacle). We can never visit any obstacle.

Input

Input consists of several cases. Every case begins with n and m, followed by n rows with c ‍characters each. The cells with an obstacle have an ‘X’, and the empty cells a period. The initial and final cells are always empty. Assume that both n and m are between 2 and 100.

Output

For every case, print the number of ways to go from the beginning to the end, as explained above. Since this number can be very large, make the computations modulo 108 + 7.

Public test cases
  • Input

    2 3
    ...
    ...
    
    3 6
    .X...X
    .XX...
    .X....
    
    10 35
    ...................................
    ...................................
    ...................................
    ...................................
    ...................................
    ...................................
    ...................................
    ...................................
    ...................................
    ...................................
    

    Output

    3
    7
    63921960
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++