Maps
Национална Олимпиада по Информатика, Кръг 3
Time Limit: 0.2s, Memory Limit: 64MiB
След задачата The Climb, Ели се зариби да ходи по планини. Сега тя тръгна с (доста голяма) група планинари. Всеки ден групата отсяда в някоя хижа и вечерта решават къде ще ходят на следващия ден. Разбира се, тъй като всички планинари искат да се изкачват, следващата хижа трябва да е със стриктно по-голяма надморска височина от текущата. Ако има повече от един избор за следваща хижа е възможно да се получи разногласие и групата се раздели на две, като едната половина отива на едно място, докато другата - на друго. Ако вече разцепили се части от първоначалната група се срещнат в дадена хижа, те не се обединяват отново, тоест винаги си остават отделени и продължават да си се цепят независимо.


N реда и M колони. Във всяка клетка на матрицата има точно по една хижа, която е с надморска височина Aij. Групата може да тръгне от произволна клетка и да се движи между всеки две (не задължително съседни) такива, стига новата да е със стриктно по-голяма надморска височина от текущата. (Забележете, че по пътя между тях планинарите могат да слизат и да се изкачват – важно е само финалната клетка да е по-висока.)
Вход
На първия ред на стандартния вход ще бъдат зададени целите числа N и M - съответно броя редове и броя колони на матрицата. На всеки от следващите N реда ще бъдат зададени по M цели числа Aij - надморската височина на съответната хижа.
Изход
На стандартния изход изведете едно цяло число - броя карти, които трябва да се закупят за да може планинарите да са подготвени за най-лошия случай. Тъй като това число може да е много голямо, изведете само остатъка му при деление на 1,000,000,007.
Ограничения
  • 1 ≤ N, M ≤ 500
  • 1 ≤ Aij ≤ 1,000,000
Примерен Вход Примерен Изход
3 4 26 17 19 26 19 21 33 19 10 13 42 28 45
Мрън!