Задачі
Дуже дружня група
Дуже дружня група
У класі \textbf{N} дівчаток та \textbf{M} хлопчиків. Класному керівнику Сніжані Денисівні потрібно вибрати групу з \textbf{L} дівчаток та \textbf{K} хлопчиків на презентацію класу. Ця група повинна бути дуже дружною, тобто кожен вибраний хлопчик повинен дружити з кожною вибраною дівчинкою. Сніжану Денисівну цікавлять всі способи це зробити, а потім вона вибере з них найкращий з її точки зору. Допоможіть їй і зайдіть загальну кількість способів сформувати дуже дружню групу дітей. Так як відповідь може бути дуже великою виведіть її по модулю \textbf{1000000007}.
\InputFile
У першому рядку вхідного файлу задано натуральні числа \textbf{N}, \textbf{M}, \textbf{L}, \textbf{K}. При цьому \textbf{L} ≤ \textbf{N} ≤ \textbf{100000} і \textbf{K} ≤ \textbf{M} ≤ \textbf{15}. Наступні \textbf{N} рядків містять по \textbf{M} символів \textbf{0} або \textbf{1} кожен. При цьому \textbf{j}-й символ \textbf{i}-го рядка рівний \textbf{1} тоді і лише тоді коли \textbf{i}-та дівчинка дружить з \textbf{j}-м хлопчиком.
\OutputFile
У єдиний рядок вихідного файлу виведіть відповідь до задачі.
Вхідні дані #1
4 3 1 1 111 101 110 010
Вихідні дані #1
8