Greg has a pad. The pad's screen is an n × m rectangle, each cell can be either black or white. We'll consider the pad rows to be numbered with integers from 1 to n from top to bottom. Similarly, the pad's columns are numbered with integers from 1 to m from left to right.

Greg thinks that the pad's screen displays a cave if the following conditions hold:

  * There is a segment [l, r] (1 ≤ l ≤ r ≤ n), such that each of the rows l, l + 1, ..., r has exactly two black cells and all other rows have only white cells. 
  * There is a row number t (l ≤ t ≤ r), such that for all pairs of rows with numbers i and j (l ≤ i ≤ j ≤ t) the set of columns between the black cells in row i (with the columns where is these black cells) is the subset of the set of columns between the black cells in row j (with the columns where is these black cells). Similarly, for all pairs of rows with numbers i and j (t ≤ i ≤ j ≤ r) the set of columns between the black cells in row j (with the columns where is these black cells) is the subset of the set of columns between the black cells in row i (with the columns where is these black cells). 



Greg wondered, how many ways there are to paint a cave on his pad. Two ways can be considered distinct if there is a cell that has distinct colors on the two pictures.

Help Greg.

Input

The first line contains two integers n, m — the pad's screen size (1 ≤ n, m ≤ 2000).

Output

In the single line print the remainder after dividing the answer to the problem by 1000000007 (109 + 7).

Examples

Input

1 1


Output

0


Input

4 4


Output

485


Input

3 5


Output

451
#include <stdio.h>
#include <algorithm>
#include <string.h>
#define M 250000000005
using namespace std;
__int64 map[502][502],map2[502][502],cc[502][502],dd[502];
__int64 dist[502],dis[502];
int vist[502],maxx,order[502],v[502];
void initial(int n)
{
    int i,j;
    for (i=0;i<=n;i++)
    {
        for (j=0;j<=n;j++)
        {   map[i][j]=M;
            cc[i][j]=M;
        }
    }
    return;
}

void dijkstra(int s)
{
    int i,j,k,f,h;
    __int64 min1,min2;
    for (i=1;i<=maxx;i++)
    {
        dist[i]=map[s][i];
        dis[i]=map[i][s];
        vist[i]=0;
        v[i]=0;
    }
    h=1;
    vist[s]=1;
    dist[s]=0;
    v[s]=1;
    dis[s]=0;

    for (i=1;i<=maxx;i++)
    {
        k=1;
        f=1;
        min1=M;
        min2=M;
        for (j=1;j<=maxx;j++)
        {
            if (!vist[j]&&dist[j]<min1)
            {   k=j;min1=dist[j];}
            if(!v[j]&&dis[j]<min2)
            {   f=j;min2=dis[j];}
        }
         v[f]=1;        
        vist[k]=1;
            if(min1==M&&min2==M) break;
        for (j=1;j<=maxx;j++)
        {
            
            if(!vist[j]&&dist[j]>dist[k]+map[k][j])
                dist[j]=dist[k]+map[k][j];
            if(!v[j]&&dis[j]>dis[f]+map[j][f])
                dis[j]=dis[f]+map[j][f];
        //  if(j==4&&f==2)
            //  printf("%I64d %I64d\n",dis[f],map[j][f]);
        }   
    
    }

}

int main()
{
//  freopen("D:\\in.txt","r",stdin);
    int i,j,n,a;
    scanf("%d",&n);
    for (i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            scanf("%d",&map2[i][j]);
    for (i=1;i<=n;i++)
        scanf("%d",&order[i]);
    initial(n);
    maxx=n;
    __int64 sum=0;
    for (a=n;a>=1;a--)
    {
        sum=0;
        for(i=a;i<=n;i++)
        {   
            map[order[a]][order[i]]=map2[order[a]][order[i]];
            map[order[i]][order[a]]=map2[order[i]][order[a]];
        }
    //  printf("%I64d %I64d\n",map[2][3],map[3][2]);
        dijkstra(order[a]);
        for(i=a;i<=n;i++)
        {
            cc[order[a]][order[i]]=dist[order[i]];
            cc[order[i]][order[a]]=dis[order[i]];
            //printf("%I64d ",sum);
        }

//      for (i=1;i<=n;i++)
//      {
//          for(j=1;j<=n;j++)
//              printf("%I64d  ",cc[i][j]);
//          printf("\n");
//      }
//      printf("\n\n");

        for (i=a;i<=n;i++)
        {
            for (j=a;j<=n;j++)
            {
                if(cc[order[i]][order[j]]>dis[order[i]]+dist[order[j]])
                {                   
                    cc[order[i]][order[j]]=dis[order[i]]+dist[order[j]];
                    //  printf("..%d %d\n",order[i],order[j]);  
                    
                }
//              if(order[i]==4&&order[j]==5) 
//              {
//                  printf("%I64d\n",cc[4][5]);
//                  printf("%I64d %I64d\n",dis[order[i]],dist[order[j]]);
//                  }
                sum+=cc[order[i]][order[j]];
            }
        }
        dd[a]=sum;
    }
    for(i=1;i<n;i++)
        printf("%I64d ",dd[i]);
    printf("%I64d\n",dd[n]);
    return 0;
}