fork(5) download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class Main {
  5.  
  6.     public static void main(String[] args) {
  7.         InputReader in = new InputReader(System.in);
  8.         OutputWriter out = new OutputWriter(System.out);
  9.         TaskC solver = new TaskC(in, out);
  10.         solver.solve();
  11.         out.close();
  12.     }
  13.  
  14.     static class TaskC {
  15.  
  16.         static int n;
  17.         static int m;
  18.  
  19.         static int[] inv;
  20.         static int[] fact;
  21.         static int[] invfact;
  22.  
  23.         static int[] powN;
  24.         static int[] powM;
  25.  
  26.         InputReader in;
  27.         OutputWriter out;
  28.  
  29.         TaskC(InputReader in, OutputWriter out) {
  30.             this.in = in;
  31.             this.out = out;
  32.         }
  33.  
  34.         private void solve() {
  35.             n = in.readInt();
  36.             m = in.readInt();
  37.             precalc();
  38.             int ans = 0;
  39.             int choosePath = 1;
  40.             for(int k = 1; k < n; ++k) {
  41.                 if (k > m) break;
  42.                 int cur = MathUtil.mul(choosePath, cayley(n, k + 1));
  43.                 cur = MathUtil.mul(cur, binom(m - 1, k - 1));
  44.                 cur = MathUtil.mul(cur, powM[n - k - 1]);
  45.                 choosePath = MathUtil.mul(choosePath, n - k - 1);
  46.                 ans = MathUtil.sum(ans, cur);
  47.             }
  48.             out.print(ans);
  49.         }
  50.  
  51.         private int cayley(int n, int k) {
  52.             if (n - k - 1 < 0) {
  53.                 return MathUtil.mul(k, MathUtil.binPow(n, MathUtil.mod - 2));
  54.             }
  55.             return MathUtil.mul(k, powN[n - k - 1]);
  56.         }
  57.  
  58.         private int binom(int n, int k) {
  59.             return MathUtil.mul(fact[n], MathUtil.mul(invfact[k], invfact[n - k]));
  60.         }
  61.  
  62.         private void precalc() {
  63.             powN = new int[n + 1];
  64.             powM = new int[n + 1];
  65.             powN[0] = 1;
  66.             powM[0] = 1;
  67.             for(int i = 1; i <= n; ++i) {
  68.                 powN[i] = MathUtil.mul(powN[i - 1], n);
  69.                 powM[i] = MathUtil.mul(powM[i - 1], m);
  70.             }
  71.  
  72.             inv = new int[m + 1];
  73.             fact = new int[m + 1];
  74.             invfact = new int[m + 1];
  75.             inv[0] = inv[1] = 1;
  76.             fact[0] = fact[1] = 1;
  77.             invfact[0] = invfact[1] = 1;
  78.             for(int i = 2; i <= m; ++i) {
  79.                 inv[i] = MathUtil.mul(inv[MathUtil.mod % i], MathUtil.mod - MathUtil.mod / i);
  80.                 fact[i] = MathUtil.mul(fact[i - 1], i);
  81.                 invfact[i] = MathUtil.mul(invfact[i - 1], inv[i]);
  82.             }
  83.         }
  84.     }
  85.     static class MathUtil {
  86.         private static final int mod = 1_000_000_007;
  87.  
  88.         static int binPow(int a, int n) {
  89.             int result = 1;
  90.             while (n > 0) {
  91.                 if (n % 2 == 1) {
  92.                     result = mul(result, a);
  93.                 }
  94.                 n /= 2;
  95.                 a = mul(a, a);
  96.             }
  97.             return result;
  98.         }
  99.  
  100.         static int mul(int a, int b) {
  101.             return (int)((long)a * b % mod);
  102.         }
  103.  
  104.         static int sum(int a, int b) {
  105.             int result = a + b;
  106.             if (result >= mod) result -= mod;
  107.             return result;
  108.         }
  109.  
  110.     }
  111.  
  112.     static class OutputWriter {
  113.         private final PrintWriter writer;
  114.  
  115.         public OutputWriter(OutputStream outputStream) {
  116.             writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
  117.         }
  118.  
  119.         public OutputWriter(Writer writer) {
  120.             this.writer = new PrintWriter(writer);
  121.         }
  122.  
  123.         public void print(Object... objects) {
  124.             for (int i = 0; i < objects.length; i++) {
  125.                 if (i != 0) {
  126.                     writer.print(' ');
  127.                 }
  128.                 writer.print(objects[i]);
  129.             }
  130.             writer.println();
  131.         }
  132.  
  133.         public void close() {
  134.             writer.close();
  135.         }
  136.  
  137.     }
  138.  
  139.     static class InputReader {
  140.         private InputStream stream;
  141.         private byte[] buf = new byte[1024];
  142.         private int curChar;
  143.         private int numChars;
  144.         private InputReader.SpaceCharFilter filter;
  145.  
  146.         public InputReader(InputStream stream) {
  147.             this.stream = stream;
  148.         }
  149.  
  150.         public int read() {
  151.             if (numChars == -1) {
  152.                 throw new InputMismatchException();
  153.             }
  154.             if (curChar >= numChars) {
  155.                 curChar = 0;
  156.                 try {
  157.                     numChars = stream.read(buf);
  158.                 } catch (IOException e) {
  159.                     throw new InputMismatchException();
  160.                 }
  161.                 if (numChars <= 0) {
  162.                     return -1;
  163.                 }
  164.             }
  165.             return buf[curChar++];
  166.         }
  167.  
  168.         public int readInt() {
  169.             int c = read();
  170.             while (isSpaceChar(c)) {
  171.                 c = read();
  172.             }
  173.             int sgn = 1;
  174.             if (c == '-') {
  175.                 sgn = -1;
  176.                 c = read();
  177.             }
  178.             int res = 0;
  179.             do {
  180.                 if (c < '0' || c > '9') {
  181.                     throw new InputMismatchException();
  182.                 }
  183.                 res *= 10;
  184.                 res += c - '0';
  185.                 c = read();
  186.             } while (!isSpaceChar(c));
  187.             return res * sgn;
  188.         }
  189.  
  190.         public boolean isSpaceChar(int c) {
  191.             if (filter != null) {
  192.                 return filter.isSpaceChar(c);
  193.             }
  194.             return isWhitespace(c);
  195.         }
  196.  
  197.         public static boolean isWhitespace(int c) {
  198.             return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  199.         }
  200.  
  201.         public double readDouble() {
  202.             int c = read();
  203.             while (isSpaceChar(c)) {
  204.                 c = read();
  205.             }
  206.             int sgn = 1;
  207.             if (c == '-') {
  208.                 sgn = -1;
  209.                 c = read();
  210.             }
  211.             double res = 0;
  212.             while (!isSpaceChar(c) && c != '.') {
  213.                 if (c == 'e' || c == 'E') {
  214.                     return res * Math.pow(10, readInt());
  215.                 }
  216.                 if (c < '0' || c > '9') {
  217.                     throw new InputMismatchException();
  218.                 }
  219.                 res *= 10;
  220.                 res += c - '0';
  221.                 c = read();
  222.             }
  223.             if (c == '.') {
  224.                 c = read();
  225.                 double m = 1;
  226.                 while (!isSpaceChar(c)) {
  227.                     if (c == 'e' || c == 'E') {
  228.                         return res * Math.pow(10, readInt());
  229.                     }
  230.                     if (c < '0' || c > '9') {
  231.                         throw new InputMismatchException();
  232.                     }
  233.                     m /= 10;
  234.                     res += (c - '0') * m;
  235.                     c = read();
  236.                 }
  237.             }
  238.             return res * sgn;
  239.         }
  240.  
  241.         public interface SpaceCharFilter {
  242.             public boolean isSpaceChar(int ch);
  243.         }
  244.  
  245.     }
  246. }
  247.  
Runtime error #stdin #stdout #stderr 0.05s 2184192KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Exception in thread "main" java.util.InputMismatchException
	at Main$InputReader.read(Main.java:152)
	at Main$InputReader.readInt(Main.java:171)
	at Main$TaskC.solve(Main.java:35)
	at Main$TaskC.access$000(Main.java:14)
	at Main.main(Main.java:10)
https://ideone.com/vbiC9L
language:
Java (HotSpot 12)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!