Чудова таблиця

Limits: 5 sec., 512 MiB

Зеник і Марічка написали на шматку паперу прямокутну таблицю чисел у якій \(n\) рядків та \(m\) стовпців. Вони розуміють, що таблиця чудова, але поки не знають, наскільки чудовою вона є.

Назвемо чудовістю таблиці кількість рядків, котрі утворюють неспадну послідовність (таку послідовність, у якій для кожної пари сусідніх елементів правіший елемент є більшим або рівним за лівіший).

Зеник і Марічка можуть довільним чином переставляти числа у кожному стовпці своєї таблиці. Для кожної чудовості таблиці від 0 до \(n\) вам необхідно визначити, скільки різних таблиць з такою чудовістю можна отримати. Дві таблиці вважаємо різними, якщо хоча б у одній відповідній комірці у них записані різні числа. Оскільки кількості можуть бути дуже великими, виведіть остачу від ділення кожної кількості на \(10^9 + 7\).

Input

У першому рядку задано два цілі числа \(n\) та \(m\) розділені пропуском — кількість рядків та стовпців таблиці, відповідно.

Наступні \(n\) рядків містять по \(m\) цілих чисел розділених пропусками — числа \(a_{ij}\) записані у відповідному рядку таблиці.

Output

В одному рядку виведіть \(n + 1\) ціле число — остачі від ділення кількості таблиць з чудовостями від 0 до \(n\) на \(10^9 + 7\).

Constraints

\(2 \le n \le 11\),

\(2 \le m \le 74\),

\(1 \le a_{ij} \le 10^9\).

Samples