由于账号的分数被 SuB 清零了，破防的炸鱼勾们将 SuB 开盒，并决定线下真实他。好在，SuB 有自己的秘密基地，他能躲过炸鱼勾的追杀吗？
在一条宽为 $n$ ，长为 $m$ 的大街上，SuB 住在大街一头的第 $y$ 个房间里 ，秘密基地在大街另一头的第 $y$ 个房间。
为了迷惑炸鱼勾，SuB 在逃亡的过程中会时不时地左右横跳；并且由于他不喜欢平的（even），他每一步只会向前跨过奇数（odd）格。
最后，SuB 躲进了他的秘密基地，为了基地的隐蔽性，基地大门6位密码锁的密码被设置为路径方案数的后 $6$ 位。
炸鱼勾由于长期炸鱼已经变得愚笨，凭他们那可怜的大脑并不能进入 SuB 的秘密基地，于是他们找到了你，希望你能帮助他们解开基地的密码。
在一个 $n$ 行 $m$ 列的方格图上，起点为 $(y,1)$ ，终点为 $(y,m)$，从起点向右走任意步，每一步可以从 $(i,j)$ 到达 $(i-1,j+k),(i,j+k),(i+1,j+k)$，其中 $k$ 为奇数。
方案数指从起点到达终点的所有不同走法的数量 $p$ 。
你应该输出一个6位的数字 $p' = p \bmod 1000000$ 。
第一行 $2$ 个数 $n$ 和 $m$ ，表示大街的宽度和长度；
第二行一个数 $y$ ，表示家所在的行号。
一行 $1$ 个数 $p'$ ，表示秘密基地的密码。
3 5
1000013到达第 $5$ 列第 $1 \sim n$ 行的方案数分别为 $13,16,10$ 。