Таблица
Вам дана таблица n×n, где каждый квадрат содержит целое число от 1 до n×n.
Путь в таблице начинается с некоторого квадрата и всегда идет либо по вертикали, либо по горизонтали в другой квадрат с меньшим номером, чем текущий квадрат. Квадраты не обязательно должны быть соседними, и путь может состоять только из одного квадрата.
Сколько различных путей в таблице? Поскольку ответ может быть большим, выведите его остаток при делении ответа на 10^9+7.
Входные данные:
Первая строка содержит целое число n: размер сетки.
Следующие n строк содержат по n целых чисел: содержимое сетки.
Выходные данные:
Выведите одно целое число: количество путей по модулю 10^9+7.
Пример:
Входные данные:
3
2 1 3
1 1 1
9 2 7
Выходные данные:
46
ОГРАНИЧЕНИЯ : 1 ≤ n ≤ 1000


Объяснение: В этом примере возможны, среди прочего, следующие три пути.