Важно обавештење: одржава се концерт најпознатијих извођача рок музике на коме учествују Рибља Чорба, Бајага, Рокери с Мораву, Дејан Цукић и Ријана! Органи реда су добили информацију да су неки учесници Државног такмичења из информатике (уједно и љубитељи турбо-фолка) одлучили да се инфилтрирају међу публиком и праве нереде певајући песме Драгане Мирковић, Шемсе Суљаковића и Тејлор Свифт.

Простор на коме је публика можемо замислити као матрицу са \(n\) редова (нумерисаних од \(1\) до \(n\) одозго надоле) и \(m\) колона где је ред број \(1\) први ред, непосредно испред извођача, а ред број \(n\) је последњи ред. Свако поље матрице је или слободно (означено знаком ‘\(0\)’) или заузето од стране неке особе (означено знаком ‘\(1\)’). Када такмичар дође на концерт он изабере неко слободно поље у последњем реду и стане тамо (ако таквих поља нема, иде кући). Након тога, у једном потезу може урадити једну од следеће 2 ствари:

• Помери се за једно поље изнад (у ред испред) уколико је то поље слободно; или
• Помери се за једно поље улево или удесно (у истом реду). Приликом померања улево/удесно такмичар може гурати једну или више особа у одговарајућем смеру (или се само померити на одговарајуће поље ако је слободно); прецизније, ако је снага такмичара \(k\), тада, уколико се непосредно лево од такмичара налази узастопна група од \(a\) (\(a \geq 0\)) особа након које постоји бар једно слободно поље, могуће је померити се улево за једно поље, при чему се цела група од \(a\) особа такође помера за по једно поље улево, ако и само ако је \(a \leq k\). Исто важи и за померање удесно. Није дозвољено гурати људе ван матрице.

Такмичар жели да неким низом потеза дође до неког поља у првом реду али тако да ниједно поље не посети више од једном. Чим први пут дође до неког поља у првом реду, он више не прави потезе већ креће да брејк-денсује и пева “Цветак зановетак”; његов циљ је остварен.

Одредити на колико начина такмичар може остварити свој циљ и исписати тај број по модулу \(10^9+7\).

Опис улаза

У првом реду стандардног улаза налазе се цели бројеви \(n\), \(m\) и \(k\), редом, где су \(n\) и \(m\) димензије матрице а \(k\) снага такмичара. У наредних \(n\) редова, налази се по \(m\) карактера, без размака, од којих је сваки ‘\(0\)’ или ‘\(1\)’ - опис простора на коме је публика.

Опис излаза

У једином реду стандардног излаза исписати број начина на које такмичар може остварити свој циљ по модулу \(10^9+7\).

Ограничења

• \(2 \leq n, m \leq 2000\)
• \(0 \leq k \leq m\)
• Сви карактери матрице из улаза ће бити ‘\(0\)’ или ‘\(1\)’.

Подзадаци

1. (7 поена) Нема људи у публици, тј. сви карактери улазне матрице ће бити ‘\(0\)’.
2. (11 поена) \(n,m \leq 7\).
3. (15 поена) \(k = 0\).
4. (22 поена) \(n, m \leq 400\)
5. (45 поена) Без додатних ограничења.

Примери

Пример 1

Улаз

3 9 3
010001100
101011010
011101110

Излаз

7

Објашњење

Имамо 3 реда и у сваком реду по 9 поља; снага такмичара је 3. Означимо са ‘U’ потез нагоре, са ‘L’ потез улево и са ‘R’ потез удесно. Ако се крене из поља (3,1), сви начини су: RURU и RURRU; ако се крене из поља (3,5), сви начини су: LUU, LULU, LURU; ако се крене из поља (3, 9), сви начини су: UU и ULU. Ово је укупно \(7\) mod \((10^9 + 7) = 7\) начина. Приметимо нпр да кретања RUU и RURRRU из поља (3,1) нису валидна - прво јер у трећем потезу није могуће ићи нагоре када је поље изнад заузето а друго јер у петом потезу такмичар не може гурати 4 особе јер му је снага 3.

Пример 2

Улаз

4 5 1
11000
00110
01001
10001

Излаз

0