Problem: Peppa the Pig was walking and walked into the forest. What a strange coincidence! The forest has the shape of a rectangle, consisting of n rows and m columns. We enumerate the rows of the rectangle from top to bottom with numbers from 1 to n, and the columns — from left to right with numbers from 1 to m. Let's denote the cell at the intersection of the r-th row and the c-th column as (r, c).

Initially the pig stands in cell (1, 1), and in the end she wants to be in cell (n, m). Since the pig is in a hurry to get home, she can go from cell (r, c), only to either cell (r + 1, c) or (r, c + 1). She cannot leave the forest.

The forest, where the pig is, is very unusual. Some cells of the forest similar to each other, and some look very different. Peppa enjoys taking pictures and at every step she takes a picture of the cell where she is now. The path through the forest is considered to be beautiful if photographs taken on her way, can be viewed in both forward and in reverse order, showing the same sequence of photos. More formally, the line formed by the cells in order of visiting should be a palindrome (you can read a formal definition of a palindrome in the previous problem).

Count the number of beautiful paths from cell (1, 1) to cell (n, m). Since this number can be very large, determine the remainder after dividing it by 109 + 7.

Input

The first line contains two integers n, m (1 ≤ n, m ≤ 500) — the height and width of the field.

Each of the following n lines contains m lowercase English letters identifying the types of cells of the forest. Identical cells are represented by identical letters, different cells are represented by different letters.

Output

Print a single integer — the number of beautiful paths modulo 109 + 7.

Examples

Input

3 4
aaab
baaa
abba


Output

3

Note

Picture illustrating possibilities for the sample test. 

<image>

<image>

<image>

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Artem Gilmudinov
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Reader in = new Reader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskE {
        int n;
        int m;
        int[][] dUp = {{0, -1}, {-1, 0}};
        int[][] dBottom = {{1, 0}, {0, 1}};

        public void solve(int testNumber, Reader in, PrintWriter out) {
            n = in.ni();
            m = in.ni();
            String[] s = new String[n];
            for (int i = 0; i < n; i++) {
                s[i] = in.rl();
            }
            int mod = 1_000_000_007;
            if (n == 1 && m == 1) {
                out.println(1);
                return;
            }
            int len = m + n - 1;
            int max = Math.max(n, m);

            int[][] dp = new int[max][max];
            int[][] prev = new int[max][max];
            ArrayList<PairInt> upPoints = new ArrayList<>();
            ArrayList<PairInt> bottomPoints = new ArrayList<>();
            if (len % 2 == 0) {
                PairInt startPoint = null;
                if (n >= len / 2) {
                    startPoint = new PairInt(len / 2 - 1, 0);
                } else {
                    startPoint = new PairInt(n - 1, len / 2 - n);
                }
                int x = startPoint.x;
                int y = startPoint.y;
                upPoints.add(startPoint);
                while (x != 0 && y != m - 1) {
                    --x;
                    ++y;
                    upPoints.add(new PairInt(x, y));
                }
                for (PairInt pairInt : upPoints) {
                    if (check(pairInt.x + 1, pairInt.y)) {
                        bottomPoints.add(new PairInt(pairInt.x + 1, pairInt.y));
                    }
                }
                PairInt lastPoint = upPoints.get(upPoints.size() - 1);
                if (check(lastPoint.x, lastPoint.y + 1)) {
                    bottomPoints.add(new PairInt(lastPoint.x, lastPoint.y + 1));
                }
                for (int i = 0; i < upPoints.size(); i++) {
                    PairInt first = upPoints.get(i);
                    for (int j = 0; j < bottomPoints.size(); j++) {
                        PairInt second = bottomPoints.get(j);
                        if (first.x + 1 == second.x && first.y == second.y) {
                            if (s[first.x].charAt(first.y) == s[second.x].charAt(second.y)) {
                                ++prev[i][j];
                            }
                        }
                        if (first.x == second.x && first.y + 1 == second.y) {
                            if (s[first.x].charAt(first.y) == s[second.x].charAt(second.y)) {
                                ++prev[i][j];
                            }
                        }
                    }
                }
            } else {
                PairInt startPoint = null;
                if (n >= len / 2 + 1) {
                    startPoint = new PairInt(len / 2, 0);
                } else {
                    startPoint = new PairInt(n - 1, len / 2 - n + 1);
                }
                int x = startPoint.x;
                int y = startPoint.y;
                upPoints.add(startPoint);
                bottomPoints.add(startPoint);
                prev[0][0] = 1;
                while (x != 0 && y != m - 1) {
                    --x;
                    ++y;
                    upPoints.add(new PairInt(x, y));
                    bottomPoints.add(new PairInt(x, y));
                    prev[upPoints.size() - 1][upPoints.size() - 1] = 1;
                }
            }
//        out.println(upPoints);
//        out.println(bottomPoints);
            int[][] used = new int[n][m];
            int left = (len % 2 == 0 ? len / 2 - 1 : len / 2);
//        out.println(left);
//        out.println(Arrays.deepToString(prev));
            long start = System.currentTimeMillis();
            while (left-- > 0) {
                int size1, size2;
                size1 = upPoints.size();
                size2 = bottomPoints.size();
                for (int i = 0; i < size1; i++) {
                    for (int j = 0; j < size2; j++) {
                        dp[i][j] = 0;
                    }
                }
                ArrayList<PairInt> newUpPoints = new ArrayList<>();
                ArrayList<PairInt> newBottomPoints = new ArrayList<>();
                ArrayList<ArrayList<PairInt>> adjPointsUp = new ArrayList<>();
                ArrayList<ArrayList<PairInt>> adjPointsBottom = new ArrayList<>();
                int upiter, bottomiter;
                upiter = bottomiter = 1;
                for (PairInt pairInt : upPoints) {
                    ArrayList<PairInt> list = new ArrayList<>();
                    adjPointsUp.add(list);
                    for (int z = 0; z < 2; z++) {
                        if (check(pairInt.x + dUp[z][0], pairInt.y + dUp[z][1])) {
                            PairInt res = new PairInt(pairInt.x + dUp[z][0], pairInt.y + dUp[z][1]);
                            list.add(res);
                            if (used[res.x][res.y] == 0) {
                                used[res.x][res.y] = upiter++;
                                newUpPoints.add(res);
                            }
                        }
                    }
                }
                for (PairInt pairInt : bottomPoints) {
                    ArrayList<PairInt> list = new ArrayList<>();
                    adjPointsBottom.add(list);
                    for (int z = 0; z < 2; z++) {
                        if (check(pairInt.x + dBottom[z][0], pairInt.y + dBottom[z][1])) {
                            PairInt res = new PairInt(pairInt.x + dBottom[z][0], pairInt.y + dBottom[z][1]);
                            list.add(res);
                            if (used[res.x][res.y] == 0) {
                                used[res.x][res.y] = bottomiter++;
                                newBottomPoints.add(res);
                            }
                        }
                    }
                }
                int upIndex, bottomIndex, prevValue;
                for (int i = 0; i < size1; i++) {
                    ArrayList<PairInt> listUp = adjPointsUp.get(i);
                    for (int j = 0; j < size2; j++) {
                        ArrayList<PairInt> listBottom = adjPointsBottom.get(j);
                        prevValue = prev[i][j];
                        if (prevValue == 0) {
                            continue;
                        }
                        for (PairInt upPoint : listUp) {
                            upIndex = used[upPoint.x][upPoint.y] - 1;
                            for (PairInt bottomPoint : listBottom) {
                                bottomIndex = used[bottomPoint.x][bottomPoint.y] - 1;
                                if (s[upPoint.x].charAt(upPoint.y) == s[bottomPoint.x].charAt(bottomPoint.y)) {
                                    dp[upIndex][bottomIndex] = (dp[upIndex][bottomIndex] + prevValue) % mod;
                                }
                            }
                        }
                    }
                }

                for (int i = 0; i < max; i++) {
                    System.arraycopy(dp[i], 0, prev[i], 0, max);
                }
                upPoints = newUpPoints;
                bottomPoints = newBottomPoints;
//            out.println(adjPointsUp);
//            out.println(adjPointsBottom);
//            out.println(upPoints);
//            out.println(bottomPoints);
//            out.println(Arrays.deepToString(used));
//            out.println(Arrays.deepToString(dp));
//            out.println("----");
            }
            out.println(dp[used[0][0] - 1][used[n - 1][m - 1] - 1]);
            //out.println(System.currentTimeMillis() - start);
        }

        public boolean check(int x, int y) {
            return x >= 0 && x < n && y >= 0 && y < m;
        }

    }

    static class PairInt {
        public int x;
        public int y;

        public PairInt(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public String toString() {
            return x + " " + y;
        }

        public PairInt clone() {
            return new PairInt(x, y);
        }

    }

    static class Reader {
        private BufferedReader in;
        private StringTokenizer st = new StringTokenizer("");
        private String delim = " ";

        public Reader(InputStream in) {
            this.in = new BufferedReader(new InputStreamReader(in));
        }

        public String next() {
            if (!st.hasMoreTokens()) {
                st = new StringTokenizer(rl());
            }
            return st.nextToken(delim);
        }

        public String rl() {
            try {
                return in.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        public int ni() {
            return Integer.parseInt(next());
        }

    }
}