[Java知识库]第十三届蓝桥杯大赛软件赛省赛第二场（Java 大学A组）

??太久没写题了，调下状态。

试题 A: 练习

本题总分：$5$ 分

【问题描述】

??小蓝在蓝桥杯练习系统上做题。做到一道题，他编写好程序，在自己的电脑上尝试了题目中提供的几个样例，全部得到了正确的结果，可是当他将自己的程序提交到练习系统上时，却得了 $0$ 分，这种情况可能的原因是什么？请在以下选项中选择所有可能导致这种情况的原因。

??$\mathrm{A}.$ 题目中的样例一般比较小，在评测的时候可能使用的评测用例比较大，小蓝的程序虽然在小样例能得到解，对于大一些的评测用例可能速度太慢，超过了题目要求的时间限制。

??$\mathrm{B}.$ 小蓝的内存使用过多，虽然在自己的电脑上运行正确，可是在评测的内存限制下无法运行。

??$\mathrm{C}.$ 小蓝的程序有考虑不足之处，题目中的样例比较小，小蓝的程序恰好能得到对应的结果，可是当评测用例比较复杂时，小蓝的程序无法得到正确的结果。

【答案提交】

??这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个由大写字母组成的字符串，按字母顺序给出所选择的选项，在提交答案时只填写这个字符串，填写多余的内容将无法得分。例如，如果选项全部正确，请填写答案 $\mathrm{A}\mathrm{B}\mathrm{C}$。

ABC

试题 B: 超级质数

本题总分：$5$ 分

【问题描述】

??如果一个质数 $P$ 的每位数字都是质数，而且每两个相邻的数字组成的两位数是质数，而且每三位相邻的数字组成的三位数是质数，依次类推，如果每相邻的 $k$ 位数字组成的 $k$ 位数都是质数，则 $P$ 称为超级质数。

??如果把超级质数 $P$ 看成一个字符串，则这个超级质数的每个子串都是质数。

??例如，$53$ 是一个超级质数。

??请问，最大的超级质数是多少？

【答案提交】

??这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

373

递推

??若 $n$ 是质数，而 $?\frac{n}{10}?、n?10^{?{\log }_{10}n?}?\frac{n}{10^{?{\log }_{10}n?}}?$ 同为超级质数，则 $n$ 同为超级质数。

??递推就完事了。

import java.util.*;

public class Test {

    public static void main(String[] args) { new Test().run(); }

    int[] P = { 2, 3, 5, 7 };

    long ans = 0;

    void run() {
        Queue<Long> queue = new ArrayDeque();
        HashMap<Long, Long> map = new HashMap();
        for (long p : P) {
            queue.offer(p);
            map.put(p, p);
        }
        while (!queue.isEmpty()) {
            long now = queue.poll();
            long head = map.get(now);
            long buff = (now - head) * 10;
            ans = Math.max(ans, now);
            for (long p : P) {
                long temp = now * 10 + p;
                if (millerRabin(temp) &&
                    map.containsKey(buff + p)) {
                    map.put(temp, head * 10);
                    queue.offer(temp);
                }
            }
        }
        System.out.println(ans);
    }

    int time = 50;
    
    boolean millerRabin(long n) {
        if (n % 2 == 0) return n == 2;
        long b = n - 1;
        int k = 0;
        for (; b % 2 == 0; ++k, b /= 2);
        for (int i = 0, j; i < time; ++i) {
            long a = (int)(Math.random() * (n - 1) + 1);
            long v = qpow(a, b, n);
            if (v == 1) continue;
            for (j = 0; j < k; ++j) {
                if (v == n - 1) break;
                v = multi(v, v, n);
            }
            if (j == k) return false;
        }
        return true;
    }

    long multi(long a, long b, long p) {
        long prod = 0;
        while (b > 0) {
            if (b % 2 == 1) prod = (prod + a) % p;
            a = (a + a) % p;
            b >>= 1;
        }
        return prod;
    }

    long qpow(long a, long b, long p) {
        long pow = 1;
        while (b > 0) {
            if (b % 2 == 1) pow = multi(pow, a, p);
            a = multi(a, a, p);
            b >>= 1;
        }
        return pow;
    }
}

试题 C: 考勤刷卡

时间限制: $3.0\mathrm{s}$?内存限制: $512.0\mathrm{M}\mathrm{B}$?本题总分：$10$ 分

【问题描述】

??小蓝负责一个公司的考勤系统，他每天都需要根据员工刷卡的情况来确定每个员工是否到岗。

??当员工刷卡时，会在后台留下一条记录，包括刷卡的时间和员工编号，只要在一天中员工刷过一次卡，就认为他到岗了。

??现在小蓝导出了一天中所有员工的刷卡记录，请将所有到岗员工的员工编号列出。

【输入格式】

??输入的第一行包含一个正整数 $n$，表示一天中所有员工的刷卡记录的条数。

??接下来 $n$ 行，每行包含一条刷卡记录，每条刷卡记录的格式为：

??$\mathrm{H}\mathrm{H}:\mathrm{M}\mathrm{M}:\mathrm{S}\mathrm{S}\mathrm{I}\mathrm{D}$

??其中 $\mathrm{H}\mathrm{H}:\mathrm{M}\mathrm{M}:\mathrm{S}\mathrm{S}$ 表示刷卡时间，$\mathrm{H}\mathrm{H}$ 为一个 $0$ 到 $23$ 之间的两位十进制整数（可能含前导 $0$）表示时，$\mathrm{M}\mathrm{M}$ 为一个 $0$ 到 $59$ 之间的两位十进制整数（可能含前导 $0$）表示分，$\mathrm{S}\mathrm{S}$ 为一个 $0$ 到 $59$ 之间的两位十进制整数（可能含前导 $0$）表示秒，$\mathrm{I}\mathrm{D}$ 为一个不含前导 $0$ 的整数表示员工的编号。

??所有记录按照刷卡时间升序排列，可能同一时刻有多人刷卡。

【输出格式】

??输出若干行，每行包含一个整数，按照从小到大的顺序输出，表示到岗员工的编号。

【样例输入】

4
13:05:42 103
14:07:12 4567
15:03:00 103
17:00:21 1

【样例输出】

1
103
4567

【评测用例规模与约定】

??对于 $50\%$ 的评测用例，$1\le n\le 100$。
??对于所有评测用例，$1\le n\le 10000$，员工编号为不超过 $10^9$ 的正整数。

??感觉有诈，但读了几遍也没瞅着陷阱，

??鉴定为纯纯的签到。

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.TreeSet;
import java.util.Set;

public class Main {

    public static void main(String[] args) { new Main().run(); }

    void run() {
        try (BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
             PrintWriter out = new PrintWriter(System.out)) {
            int n = Integer.parseInt(in.readLine());
            Set<Integer> set = new TreeSet();
            while (n-- > 0) {
                String line = in.readLine();
                set.add(Integer.parseInt(
                    line.substring(line.indexOf(0x20) + 1)
                ));
            }
            for (Integer id : set) out.println(id);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

试题 D: 最大和

时间限制: $3.0\mathrm{s}$?内存限制: $512.0\mathrm{M}\mathrm{B}$?本题总分：$10$ 分

【问题描述】

??小蓝在玩一个寻宝游戏，游戏在一条笔直的道路上进行，道路被分成了 $n$ 个方格，依次编号 $1$ 至 $n$，每个方格上都有一个宝物，宝物的分值是一个整数（包括正数、负数和零），当进入一个方格时即获得方格中宝物的分值。小蓝可以获得的总分值是他从方格中获得的分值之和。

??小蓝开始时站在方格 $1$ 上并获得了方格 $1$ 上宝物的分值，他要经过若干步到达方格 n。

??当小蓝站在方格 $p$ 上时，他可以选择跳到 $p+1$ 到 $p+D(n?p)$ 这些方格中的一个，其中 $D(1)=1，D(x)（x>1）$定义为 $x$ 的最小质因数。

??给定每个方格中宝物的分值，请问小蓝能获得的最大总分值是多少。

【输入格式】

??输入的第一行包含一个正整数 $n$。

??第二行包含 $n$ 个整数，依次表示每个方格中宝物的分值。

【输出格式】

??输出一行包含一个整数，表示答案。

【样例输入】

5
1 -2 -1 3 5

【样例输出】

8

【样例说明】
?最优的跳跃方案为$：$$1\to 3\to 4\to 5$。

【评测用例规模与约定】

??对于 $40\%$ 的评测用例，$1\le n\le 100$。
??对于 $80\%$ 的评测用例，$1\le n\le 1000$。
??对于所有评测用例，$1\le n\le 10000$，每个宝物的分值为绝对值不超过 $10^5$ 的整数。

?? 做个最简单的估计，排除掉 $2～n$ 中最小质因数为 $2$ 即奇偶性为偶的数，给上界为 $O(n^2)$ 的复杂度配上一个系数 $\frac{1}{4}$ 就能在 $3\mathrm{s}$ 内通过所有用例了。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.io.IOException;

public class Main {

    public static void main(String[] args) { new Main().run(); }
    
    void run() {
    	int n = nextInt(), a;
    	int[] prime = new int[n + 1];
    	int[] dp = new int[n + 1];
    	for (int i = 2; i <= n; ++i)
    		if (prime[i] == 0)
    			for (int j = i; j <= n; j += i)
    				if (prime[j] == 0) prime[j] = i;
    	prime[1] = 1;
    	for (int i = 1; i <= n; ++i) {
    		a = nextInt();
    		dp[i] += a;
    		for (int j = min(i + prime[n - i], n); j > i; --j)
    			if (dp[i] > dp[j]) dp[j] = dp[i];
    	}
    	System.out.println(dp[n]);
    }
    
    int min(int arg1, int arg2) { return arg1 < arg2 ? arg1 : arg2; }
    
    StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    
    int nextInt() {
    	try {
			in.nextToken();
		} catch (IOException e) {
			e.printStackTrace();
		}
		return (int)in.nval;
    }
}

试题 E: 染色时间

时间限制: $3.0\mathrm{s}$?内存限制: $512.0\mathrm{M}\mathrm{B}$?本题总分：$15$ 分

【问题描述】

??小蓝有一个 $n$ 行 $m$ 列的白色棋盘，棋盘的每一个方格都可以被染成彩色。

??每个方格有一个染色时间 $t_{ij}$，不同方格的染色时间可能不同。如果一个方格被触发了染色，这个方格就会在 $t_{ij}$ 秒之后变成彩色，然后将自己上下左右四个方向相邻的方格触发染色。每个方格只能被触发染色一次，第一次触发之后的触发为无效触发。

??给定每个方格的染色时间，在时刻 $0$ 触发第一行第一列的方格染色，请问多长时间后整个棋盘完成染色。

【输入格式】

??输入的第一行包含两个整数 $n,m$，分别表示棋盘的行数和列数。

??接下来 $n$ 行，每行 $m$ 个正整数，相邻的整数之间用一个空格分隔，表示每个方格的染色时间。该部分的第 $i$ 行第 $j$ 个整数表示 $t_{ij}$，即第 $i$ 行第 $j$ 列的方格的染色时间。

【输出格式】

??输出一行包含一个整数，表示整个棋盘完成染色的时间。

【样例输入】

2 3
1 2 3
4 5 6

【样例输出】

12

【评测用例规模与约定】

??对于 $30\%$ 的评测用例，$1\le n,m\le 10$。
??对于 $60\%$ 的评测用例，$1\le n,m\le 50$。
??对于所有评测用例，$1\le n,m\le 500$，$1\le t_{ij}\le 1000$。

??大模拟。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.io.IOException;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {

    public static void main(String[] args) { new Main().run(); }

    int[][] offset = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    void run() {
        Queue<Block> queue = new PriorityQueue();
        int n = nextInt(), m = nextInt(), ans = 0;
        int[][] clock = new int[n][m];
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                clock[i][j] = nextInt();
        queue.offer(new Block(clock[0][0], 0, 0));
        clock[0][0] = 0;
        while (!queue.isEmpty()) {
            Block now = queue.poll();
            if (now.time > ans) ans = now.time;
            for (int i = 0, x, y; i < 4; ++i) {
                x = now.x + offset[i][0];
                y = now.y + offset[i][1];
                if (x >= 0 && x < n && y >= 0 && y < m &&
                    clock[x][y] > 0) {
                    queue.offer(new Block(clock[x][y] + now.time, x, y));
                    clock[x][y] = 0;
                }
            }
        }
        System.out.println(ans);
    }

    class Block implements Comparable<Block> {

        int time, x, y;

        Block(int time, int x, int y) {
            this.time = time;
            this.x = x;
            this.y = y;
        }

        public int compareTo(Block b) {
            return this.time - b.time;
        }
    }

    StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    int nextInt() {
        try {
            in.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int)in.nval;
    }
}

试题 F: k 倍区间

时间限制: $3.0\mathrm{s}$?内存限制: $512.0\mathrm{M}\mathrm{B}$?本题总分：$15$ 分

【问题描述】

??一个整数序列 $A=(a_1,a_2,?,a_n)$ 的区间和为 $S_{i,j}=a_i+a_{i+1}+?+a_j$。

??给定整数序列 $A$ 和一个正整数 $k$，请问有多少个区间 $[i,j]$ 满足 $1\le i\le j\le n$ 且 $S_{i,j}$ 是 $k$ 非负整数倍。

【输入格式】

??输入的第一行包含两个整数 $n、k$，用一个空格分隔。

??第二行包含 $n$ 个整数 $a_1,a_2,?,a_n$，相邻的整数之间用一个空格分隔。

【输出格式】

??输出一行包含一个数表示满足条件的区间数量。

【样例输入】

7 3
1 -1 0 2 2 2 -30

【样例输出】

7

【样例说明】
?满足条件的区间有 $[1,2],[1,3],[1,6],[2,5],[3,3],[3,6],[4,6]$。

【评测用例规模与约定】

??对于 $40\%$ 的评测用例，$1\le n\le 500，1\le k\le 10$；
??对于 $60\%$ 的评测用例，$1\le n\le 2000$；
??对于所有评测用例，$1\le n\le 100000，1\le k\le 10^9，?10^9\le a_i\le 10^9$。

同余类

??设 $S_i={\sum }_{j=1}^i{a}_j$，若一对 $i,j$ 使得 $S_j?S_i$ 非负，$k|(S_j?S_i)$，则 $[i,j]$ 是一个 $k$ 倍区间，且 $S_i\equiv S_j(\mathrm{m}\mathrm{o}\mathrm{d}k)$。

??于是我们将序列 $S_1,S_2,?,S_n$ 抽离成若干个稳定的 k 的同余系，这样同余系内任意的两个不同元素，都能确定一个区间，其和为 $k$ 的一个倍数，然后顺序遍历每个同余系，用合数的方式确定当前元素的排名计入答案就行了，此举意在使确定的区间和非负。

??$\mathrm{J}\mathrm{a}\mathrm{v}\mathrm{a}$ 的 $\mathrm{T}\mathrm{r}\mathrm{e}\mathrm{e}\mathrm{S}\mathrm{e}\mathrm{t}$ 没有实现 $\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{k}()$ 方法，所以这里通过离散化树状数组组织出了类似的功能。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.io.IOException;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Main {

    public static void main(String[] args) { new Main().run(); }

    void run() {
        int n = nextInt(), m, k = nextInt(), ans = 0;
        Map<Integer, int[]> trees = new HashMap();
        Prefix[] tuple = new Prefix[n + 1];
        Prefix[] sorted = new Prefix[n + 1];
        tuple[0] = sorted[0] = new Prefix(0);
        for (int i = 1; i <= n; ++i)
            tuple[i] = sorted[i] =
                new Prefix(tuple[i - 1].sum + nextInt());
        Arrays.sort(sorted, (a, b) -> Long.compare(a.sum, b.sum));
        sorted[0].rank = 1;
        for (int i = 1; i <= n; ++i)
            if (sorted[i].sum > sorted[i - 1].sum)
                sorted[i].rank = sorted[i - 1].rank + 1;
            else sorted[i].rank = sorted[i - 1].rank;
        m = sorted[n].rank;
        for (int i = 0; i <= n; ++i) {
            int[] tree = trees.get((int)(tuple[i].sum % k));
            if (tree == null)
                trees.put((int)(tuple[i].sum % k), tree = new int[m + 1]);
            for (int j = tuple[i].rank; j > 0; j &= j - 1) ans += tree[j];
            for (int j = tuple[i].rank; j <= m; j += j & -j) ++tree[j];
        }
        System.out.println(ans);
    }

    class Prefix {

        int rank;

        long sum;

        Prefix(long sum) { this.sum = sum; }
    }

    StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    int nextInt() {
        try {
            in.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int)in.nval;
    }
}

试题 G: 选素数

时间限制: $3.0\mathrm{s}$?内存限制: $512.0\mathrm{M}\mathrm{B}$?本题总分：$20$ 分

【问题描述】

??给定两个正整数 $s、t$，每回合可以选择任意一个小于 $s$ 的不是 $s$ 的因子的素数 $p$，然后取最小的 $y$ 使得 $y>s$ 且 $y\mathrm{mod}p=0$，并将这个 $y$ 赋值给 $s$。

??问最多多少回合后，$s\ge t$。

【输入格式】

??输入的第一行包含一个整数 $T$ 表示询问次数。

??接下来 $T$ 行，每行包含两个整数 $s_i,t_i$，用一个空格分隔，表示一次询问。

【输出格式】

??输入 $T$ 行，每行包含一个整数，依次表示每次询问的答案。

【样例输入】

3
3 4
6 8
7 9

【样例输出】

1
1
2

【评测用例规模与约定】

??对于 $20\%$ 的评测用例，$T=1,t_i\le 10^4$；
??对于 $60\%$ 的评测用例，$1\le T\le 500,t_i\le 500000$；
??对于所有评测用例，$1\le T\le 200000,3\le s_i\le t_i\le 10^7$。

分类讨论

??当 $2?s$ 时，最多 $t?s$ 回合后，$s\ge t$，

??不会。

试题 H: 五子棋

时间限制: $5.0\mathrm{s}$?内存限制: $1.0\mathrm{G}\mathrm{B}$?本题总分：$20$ 分

【问题描述】

??小蓝和小乔正在一张 $n\times n$ 的棋盘上下五子棋，小蓝持黑先落子，之后双方轮流落子，当有一方获胜时，游戏立刻终止。

??现在给出棋盘的状态，问给出的状态是否合法。如果合法，找出是否有人获胜。如果有人获胜，找出输出胜负的决定手在哪里。如果有多个可能的决定手位置 $(x,y)$，优先输出 $x$ 最小的，$x$ 也相同时输出 $y$ 最小的。

??在本题中，只考虑最简单的规则：双方每次可以选一个未放棋子的位置放自己的棋子，当某一步落子后出现横向、或纵向、或两个 $45^o$ 方向之一有 $5$ 个或 $5$ 个以上连续的自己的棋子时获胜。

【输入格式】

??输入的第一行包含一个整数 $T$ 表示数据组数。接下来依次表示每组数据。

??对于第 $i$ 组数据，第一行包含一个整数 $n_i$，表示棋盘的大小。

??接下来 $n_i$ 行每行包含一个长度为 $n_i$ 的字符串，由 $0$ 或 $1$ 或 $.$ 组成，不包含空格或其它字符。其中 $0$ （$\mathrm{A}\mathrm{S}\mathrm{C}\mathrm{I}\mathrm{I}$ 码为 $48$）表示黑棋子，$1$ （$\mathrm{A}\mathrm{S}\mathrm{C}\mathrm{I}\mathrm{I}$ 码为 $49$）表示白棋子，$.$ （$\mathrm{A}\mathrm{S}\mathrm{C}\mathrm{I}\mathrm{I}$ 码为 $46$）表示空位。

【输出格式】

??对于每组数据，如果给定的状态不合法，那么仅输出一行包含一个英文字符串 $\mathrm{N}\mathrm{O}$。

??如果给定的状态合法，则输出两行，第一行包含一个英文字符串 $\mathrm{Y}\mathrm{E}\mathrm{S}$。如果无人获胜，第二行包含一个英文字符串 $\mathrm{D}\mathrm{R}\mathrm{A}\mathrm{W}$；否则第二行包含两个整数 $x,y$，用一个空格分隔，表示胜负的决定手的坐标为第 $x$ 行 $y$ 列。

【样例输入】

3
3
...
...
...
5
00000
.....
.....
.....
11111
5
11101
...0.
...0.
...0.
...0.

【样例输出】

YES
DRAW
NO
YES
1 4

【评测用例规模与约定】

??对于 $25\%$ 的评测用例，$\Sigma n_i\le 10$；
??对于 $50\%$ 的评测用例，$\Sigma n_i\le 100$；
??对于 $75\%$ 的评测用例，$\Sigma n_i\le 500$；
??对于所有评测用例，$1\le n_i\le 5000，\Sigma n_i\le 5000$。

??鉴定为大模拟，

??输入格式限制了输入的合法性，那么剩下的不合法状况只剩下双方同胜、连续同色棋子数大于五以及白落子比黑多（黑子说话）。

??然后按照先 $x$ 后 $y$ 的升序枚举是否有以该格为起始的连续的五个同色棋子就完了。

// 歇会

试题 ?I: 第几小

时间限制: $5.0\mathrm{s}$?内存限制: $512.0\mathrm{M}\mathrm{B}$?本题总分：$25$ 分

【问题描述】

??给定一个数组 $A=(a_1,a_2,?,a_n)$，请对该数组执行 $m$ 次修改或查询操作：

??若操作为 $1$ $x$ $y$，表示将 $a_x$ 的值修改为 $y$；

??若操作为 $2$ $l$ $r$ $p$ 表示求 $a_p$ 在 $a_l,a_{l+1},?,a_r$ 中是第几小的（比 $a_p$ 小的元素个数加 $1$）。

【输入格式】

??输入的第一行包含一个整数 $n$。

??第二行包含 $n$ 个整数 $a_1,a_2,?,a_n$，表示数组中每个数的初始值，相邻的整数之间用一个空格分隔。

??第三行包含一个整数 $m$。

??接下来 $m$ 行每行包含一个操作，可能是 $1$ $x_i$ $y_i$ 或 $2$ $l_i$ $r_i$ $p_i$，相邻的整数之间用一个空格分隔。

【输出格式】

??输出一行，包含多个整数，相邻的整数之间用一个空格分隔，依次表示第二种操作的答案。

【样例输入】

3
1 2 3
3
2 1 3 2
1 2 4
2 1 3 2

【样例输出】

2 3

【评测用例规模与约定】

??对于 $20\%$ 的评测用例，$n\le 500$；
??对于 $40\%$ 的评测用例，$n\le 5000$；
??对于所有评测用例，$1\le n\le 100000，1\le m\le 2n，1\le a_i,y_i\le 10^6，1\le x_i\le n，1\le l_i\le p_i\le r_i\le n$。

// 先挂着

试题 J: 单峰序列

时间限制: $3.0\mathrm{s}$?内存限制: $512.0\mathrm{M}\mathrm{B}$?本题总分：$25$ 分

【问题描述】

??给定 $n,m$，求有多少个不同的序列 $A$ 满足如下条件$:$

??$1.$ $A$ 中有至少 $1$ 个数、至多 $n$ 个数，且都是互不相同的正整数；

??$2.$ $A$ 中所有元素的和恰好为 $m$；

??$3.$ 存在一个下标 $k$ 使得对于 $1<i\le k$ 有 $A_{i?1}<A_i$，对于 $k<i\le n$ 有 $A_{i?1}>A_i$。

【输入格式】

??输入一行包含两个整数 $n,m$，中间用一个空格分隔。

【输出格式】

??输出一行包含一个整数表示答案，答案可能很大，请输出答案除以 $1000000007$ 的余数。

【样例输入 1】

2 3

【样例输出 1】

3

【样例说明 1】
??$A$ 可能为 $(3)、(1,2)$ 或 $(2,1)$。

【样例输入 2】

10001 20223

【样例输出 2】

259920306

【评测用例规模与约定】

??对于 $25\%$ 的评测用例，$n,m\le 10$；
??对于 $50\%$ 的评测用例，$n,m\le 300$；
??对于 $75\%$ 的评测用例，$n,m\le 5000$；
??对于所有评测用例，$1\le n,m\le 100000$。

// 先挂