eolymp
bolt
Try our new interface for solving problems
Problems

Очень дружная группа

Очень дружная группа

Time limit 2 seconds
Memory limit 64 MiB

В классе N девочек и M мальчиков. Классному руководителю Снежане Денисовне надо выбрать группу из L девочек и K мальчиков на представление класса. Эта группа должна быть очень дружной, то есть каждый выбранный мальчик должен дружить с каждой выбранной девочкой. Снежану Денисовну интересуют все способы это сделать, а потом она выберет из них наилучший с её точки зрения. Помогите ей и найдите общее число способов сформировать очень дружную группу детей. Так как ответ может быть очень большим выведите его по модулю 1000000007.

Input data

В первой строке входного файла заданы натуральные числа N, M, L, K. При этом LN100000 и KM15. Следующие N строк содержат по M символов 0 или 1 каждая. При этом j-й символ i-й строки равен 1 тогда только тогда когда i-я девочка дружит с j-м мальчиком.

Output data

В единственную строку выходного файла выведите ответ на задачу.

Examples

Input example #1
4 3 1 1
111
101
110
010 
Output example #1
8
Author Anton Lunev
Source Winter School, Kharkov, 2011, Day 6