It seems like in test 7 n=300, m=300, k=0. Answer is obviously 709227659, but it gives WA.

I also got answer 709227659 to this testcase.
Yes, seems like incorrect tests or incorrect problem statement.

Admins, please look at this issue. At least please check test 7.
Also please, clarify order of N and M values in input data (if they go in M,N order then correct statement please).

P.S.
  Also the problem is not so difficult as described in post-contest jury solutions. If problem statement is correct, it has got simple O(N*M) dp solution (based on https://en.wikipedia.org/wiki/Lindstr%C3%B6m%E2%80%93Gessel%E2%80%93Viennot_lemma principle).

Yeah, jury solution is complicated. Mine solution is a bit different, but still straightforward O(N*M*(N+M)) dp, with simple O(1) transitions from each state