Watson gives a 2-D grid to Sherlock. Rows are numbered 1 to N from top to bottom and columns are numbered 1 to M from left to right. Sherlock is at position (1,1) right now and he is free to face any direction before he starts to move. He needs to reach (N,M). In one step, he can either move downwards or rightwards. Also, he cannot make more than K turns during his whole journey. 

Note

    He can take at most K turns.
    He is free to face any direction before starting from (1, 1).

Sample Input
3
2 2 3
2 3 1
4 4 4

Sample Output
2
2
18

For this I wanted to use some recursion to find all the paths that could make it to the end. It was a "simple" task to start and then I ran into some issues with redoing the same paths over and over with different inputs, lets start off with the simpler version.

    def find_path([x, y], turns, _, n, m, k) when k < turns or x > n or y > m, do: 0
    def find_path([x, y], _, _, n, m, _) when x == n and y == m, do: 1
    
    def find_path([x, y], turns, :right, n, m, k) do
        right = find_path([x, y + 1], turns, :right, n, m, k)      # continue right: no turn added
        down = find_path([x + 1, y], turns + 1, :down, n, m, k)    # turn down: turns + 1
        rem(right + down, @mod)
    end
    
    def find_path([x, y], turns, :down, n, m, k) do
        down = find_path([x + 1, y], turns, :down, n, m, k)        # continue down: no turn added
        right = find_path([x, y + 1], turns + 1, :right, n, m, k)  # turn right: turns + 1
        rem(down + right, @mod)
    end

This will run through the paths and remove any paths that have a turn that is greater than the k that is sent to the recursive function. 

This base cases are for when we go out of bounds, or when turns is greater than the k given. The next one is for when we arrive in the correct place and return a value of 1, which means that we are in the right place.

The next functions are for when we are taking a right or downward turn. If we are coming from a :down then an other :down will change the location but not change the turns count. If you are coming from a :right then a :down will change the location and the turns. You can then follow the logic to get the other cases. In the example you are to give the answer rem 1,000,000,007 so I make sure to do that for every step. 

This was a good start to the problem but it didn't do it fast enough for the problem. I then made sure that instead of doing every step and path on its own I wanted to keep track of the different paths as there will probably be repeats. So instead of running the recursion you can store the location and turns counts and direction as keys.

     defp find_path_memo(pos, turns, dir, n, m, k, memo) do
      key = {pos, turns, dir}
  
      case Map.get(memo, key) do
        nil ->
          {value, memo} = find_path(pos, turns, dir, n, m, k, memo)
          {value, Map.put(memo, key, value)}
  
        cached ->
          {cached, memo}
      end
    end

This will store the key as a tuple with 3 values. Thus you can easily lookup the current position with direction and turns to see if you have visited it already, if you have simply return the value if not add it in and then continue on. With this new implementation you will need to change the find_path to return the tuple.

    defp find_path([x, y], turns, _dir, n, m, k, memo)
         when turns > k or x > n or y > m,
         do: {0, memo}
  
    defp find_path([x, y], _turns, _dir, n, m, _k, memo)
         when x == n and y == m,
         do: {1, memo}
  
    defp find_path([x, y], turns, :right, n, m, k, memo) do
      {right, memo} = find_path_memo([x, y + 1], turns, :right, n, m, k, memo)
      {down, memo} = find_path_memo([x + 1, y], turns + 1, :down, n, m, k, memo)
  
      value = rem(right + down, @mod)
      {value, Map.put(memo, {[x, y], turns, :right}, value)}
    end
  
    defp find_path([x, y], turns, :down, n, m, k, memo) do
      {down, memo} = find_path_memo([x + 1, y], turns, :down, n, m, k, memo)
      {right, memo} = find_path_memo([x, y + 1], turns + 1, :right, n, m, k, memo)
  
      value = rem(down + right, @mod)
      {value, Map.put(memo, {[x, y], turns, :down}, value)}
    end

As usual I will leave the printing and the input to the reader.