题目背景

探险家小贝踏入古老符文迷宫。迷宫内部布满巨石障碍，同时存在能量禁制：每次移动会消耗能量，并且前进方向受符文节律约束。小贝从入口出发前往祭坛，需要统计所有完全满足全部禁制规则的独立路径数量。

题目描述

给定 $n\times m$ 二维网格： 0：普通空地，可通行 1：巨石障碍物，禁止踏入 路径不能重复经过同一个格子 移动规则：

路径第 1 步、第 3 步、第 5 步…（奇数步）：只能向上、向右移动 路径第 2 步、第 4 步、第 6 步…（偶数步）：只能向下、向左移动

起点位置步数记为 0；第一次移动算作第 1 步

能量限制：每移动一步消耗 1 点能量；初始拥有 K 点能量。 整条路径总移动步数不能超过 K。到达终点时，可以剩余能量，但不能透支。

不存在合法路径输出 0

输入格式

第一行三个整数 $n,m,K$ ，迷宫行数、列数、初始能量上限。 接下来 n 行，每行 m 个整数（0/1）描述地图。 最后一行四个整数 $sx,sy,ex,ey$，起点、终点坐标（下标从 0 开始）。

输出格式

输出一个整数，合法路径总数。

3 3 8
0 0 0
0 0 0
0 0 0
0 0 2 2

1

数据范围与提示

$1\le n,m \le 8,\quad 1\le K \le 15$ 起点、终点保证为空地。