val dirs= intArrayOf(0,1,0,-1,0)

val dp=Array (m) {Array (n) {LongArray (maxMove+1) {-1L } } }

funoutOfBounds(i:Int,j:Int)= i<0|| i== m|| j<0|| j== n

fundfs(i:Int,j:Int,k:Int):Long {

if (outOfBounds(i, j))return1L

if (i<0|| i== m|| j<0|| j== n)return1L

if (k==0)return0L

if (dp[i][j][k]!=-1L)return dp[i][j][k]

val dirs= intArrayOf(0,1,0,-1,0)

val dp=Array (m) {Array (n) {LongArray (maxMove+1) } }

funoutOfBounds(i:Int,j:Int)= i<0|| i== m|| j<0|| j== n

for (kin1..maxMove) {

for (iin0 until m) {

for (jin0 until n) {

for (dirin0..3) {

val i2= i+ dirs[dir]

val j2= j+ dirs[dir+1]

if (outOfBounds(i2, j2))

if (i2<0|| i2== m|| j2<0|| j2== n)

dp[i][j][k]++

dp[i][j][k]= (dp[i][j][k]+ dp[i2][j2][k-1])% mod

val dirs= intArrayOf(0,1,0,-1,0)

val dp=Array(m) {Array(n) {LongArray(maxMove+1) } }

funoutOfBounds(i:Int,j:Int)= i<0|| i== m|| j<0|| j== n

for (kin1..maxMove) {

for (iin m-1 downTo0) {

for (jin n-1 downTo0) {

for (dirin0..3) {

val i2= i+ dirs[dir]

val j2= j+ dirs[dir+1]

if (outOfBounds(i2, j2))

if (i2<0|| i2== m|| j2<0|| j2== n)

dp[i][j][k]++

dp[i][j][k]= (dp[i][j][k]+ dp[i2][j2][k-1])% mod