package org.example;

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            int m = in.nextInt();
            System.out.printf("%.0f\n", slice(m + 1, n));
        }
    }

    public static double slice(int m, int n) {
        if (n == 1) {
            return m;
        }
        double temp = slice(m, n / 2);
        return ((n % 2 == 0 ? 1 : m) * temp * temp) % 1000000007;
    }
}

小强最近在研究某个飘洋过海的游戏。

游戏可以看成一个n∗mn*mn∗m的方格图，从左上角(1,1)(1, 1)(1,1)到右下角的(n,m)(n, m)(n,m)有两种地面，CCC表示为陆地SSS表示海洋，每次穿行只能到达上下左右四个格子之一，不能走到方格图之外。

在陆地之间穿行一格需要花费三点行动力，在海洋之间穿行一格需要花费2点行动力。
但是从陆地和从海洋到陆地穿行则需要5点行动力。

输入描述：
第一行输入两个整数n,m,qn, m, qn,m,q,表示方格图的大小和询问次数。
随后nnn行，每行mmm个元素每个元素为'C'或'S',详见样例。

随后q行每行四个数字bx,by,ex,eybx, by, ex, eybx,by,ex,ey，分别代表起点的坐标和终点的坐标。

输入：
4 4 2
CCCS
SSSS
CSCS
SSCC
1 1 3 4
3 1 1 3

输出
13
14

package org.example;// 本题为考试多行输入输出规范示例，无需提交，不计分。

import java.util.Scanner;

public class Main {
    private static boolean[][] isVisit;
    private static int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    private static int n, m, q, bx, by, ex, ey, nextX, nextY, currVal, result;
    private static String[] input;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        q = sc.nextInt();
        input = new String[n];
        for (int i = 0; i < n; i++) {
            input[i] = sc.next();
        }
        while (q-- > 0) {
            isVisit = new boolean[n][m];
            result = Integer.MAX_VALUE;
            bx = sc.nextInt();
            by = sc.nextInt();
            ex = sc.nextInt();
            ey = sc.nextInt();
            currVal = 0;
            BackTrace(bx, by);
            System.out.println(result);
        }
    }

    public static boolean isOk(int x, int y) {
        return x >= 0 && x < n && y >= 0 && y < m && !isVisit[x][y];
    }

    public static void BackTrace(int x, int y) {
        if (currVal >= result) {
            return;
        }
        if (x == ex && y == ey) {
            if (currVal < result) {
                result = currVal;
            }
            return;
        }
        for (int i = 0; i < 4; i++) {
            nextX = x + direction[i][0];
            nextY = y + direction[i][1];
            if (isOk(nextX, nextY)) {
                int add = 2;
                if (input[x].charAt(y) != input[nextX].charAt(nextY)) {
                    add = 5;
                } else if (input[nextX].charAt(nextY) == 'C') {
                    add = 3;
                }
                isVisit[x][y] = true;
                currVal += add;
                BackTrace(nextX, nextY);
                currVal -= add;
                isVisit[x][y] = false;
            }
        }
    }
}