개미 timer 2s memory 512MB

정올아파트 놀이터 구석엔 n*m의 격자 형태의 개미집이 있다. 

개미집의 구조는 n*m개의 방이 각각 격자 위에 놓여있고, 가로, 세로로 인접한 방 사이에는 서로 이동할 수 있는 개미 통로가 있다. 

개미들은 낮에는 열심히 이 통로를 통해 일하다가, 밤에는 한 방에 한 마리씩 들어가서 잠을 잔다. 

상수 개미는 다른 개미들이 열심히 일할 때, 혼자 자기 방에서 프로그래밍 공부를 하는 개미이다. 

그 때문에 개미 동료들은 상수 개미를 1인분도 못하는 개미라고 멸시한다.

어느 날 밤, 못된 택쌤이 상수 개미의 집을 밟아버렸다. 

개미들의 방은 튼튼하기 때문에 개미들은 다치지 않았지만, 모든 개미 통로가 무너져버렸다. 

그래서 각 방에 한 마리씩의 개미가 고립되어 버렸다. 

개미들은 새로운 통로를 파서 모든 개미 방이 연결되도록 하고자 한다. 

그런데 통로가 될 수 있는 위치들마다 지반이 다르기 때문에, 한 통로를 뚫는데 드는 비용도 각각 다르다.

다행히 상수 개미가 남들이 일하는 동안 미리 분석해놓은 데이터가 있기 때문에, 걱정할 필요가 없다. 

상수 개미가 새로 개발한 앱 하나면, 최소비용으로 개미집을 짓는 방법을 찾는 것은 간단하다. 

그러나 언제 못된 택쌤이 또 개미들을 괴롭히러 올지 모르기 때문에, 

상수 개미는 이에 한 술 더 떠서, 최소비용으로 개미집을 짓는 모든 방법의 수를 찾으려고 한다.

상수 개미를 도와, 최소 비용으로 개미집을 짓는 모든 경우의 수를 찾는 프로그램을 작성하라. 

답이 클 수가 있기 때문에, 10^9+7로 나눈 나머지를 구하여라.​