核电站

A 市发生能源危机，被迫大量使用核能发电，A 市领导决定在郊区建造核电站，但是有的地方地形复杂，无法建造核电站。

A 市可以近似成一个 N ∗ M 的矩形，用 0 , 1 表示，0 表示平地，可以建造核电站，1 表示地势复杂区，无法建造，A 市领导又不希望核电站离得过于太近，于是规定每个核电站周围 8 88 个方向的方格上都不能造核电站，如图：

由于资金短缺，最多只能建造 k kk 个核电站，求在郊区建造 k kk 个发电站的方案数

输入

第 1 行：描述郊区的大小,两个整数 N, M。

第 2~n+1 行：每行 M 个数字(0 或 1),0 表示平地,1 表示不能建造核电站的地区。

最后一行：一个整数 k,表示造的核电站个数。

输出

1 行一个整数,表示建造 k 个核电站方案数

样例输入

3 4

0 1 0 0

1 0 1 0

0 0 1 1

2

样例输出

13