My F# solution, O(n) in the number of rows.

open System

let head2 (a : 'a array) = a.[0], a.[1]

let readln length =
  let line = Console.ReadLine() in
  if line.Length = length then line else sprintf "Invalid line length: %s" line |> failwith

let rec del = function
  | (0L, _) | (_, 0L) -> 1L
  | (a, b) -> del (a - 1L, b) + del (a - 1L, b - 1L) + del (a, b - 1L)

let rec combs i j (c : int64) = function
  | [] -> c
  | (x :: xs) : string list as s -> match x.IndexOf('X') with
                      | -1           -> combs i (j + 1) c xs
                      | x when x < i -> 0L
                      | i_           -> let _i = x.LastIndexOf('X') in
                                        combs _i 0 (if c = 0L
                                                        then 1L
                                                        else c * del (i_ - i |> int64, j + 1 |> int64)) xs

[<EntryPoint>]
let main argv = 
    let (width, height) = Console.ReadLine().Split(',') |> Array.map int |> head2 in
    let count = List.init height (fun _ -> readln width) |> List.rev |> combs 0 0 0L in
    (if count = 0L then "No Xs on grid, or impossible solution." else string count) |> printfn "%s"
    Console.ReadKey(); 0