CyclesNumber

import java.util.*;

public class CyclesNumber {
  static final int N = 100_000;
  static final int M = 305;
  static final int T = 300;
  static final int mod = 1_000_000_007;

  int add(int x, int y) {
    x += y;
    if (x >= mod)
      x -= mod;
    return x;
  }

  int mul(int x, int y) {
    return (int) (((long) x * (long) y) % mod);
  }

  boolean order(int l, int m, int r) {
    return l <= m && m <= r;
  }

  int pow(int x, int to) {
    int ans = 1;
    for (int i = 0; i < to; ++i)
      ans = mul(ans, x);
    return ans;
  }

  public String checkData(int[] n, int[] m) {
    if (n.length != m.length)
      return "n and m must contain the same nubmer of elements.";

    if (!order(1, n.length, T))
      return "n must contain between 1 and 300 integers, inclusive.";

    for (int x : n)
      if (!order(1, x, N))
        return "Each element of n must be between 1 and 100,000, inclusive.";

    for (int x : m)
      if (!order(0, x, 300))
        return "Each element of m must be between 0 and 300, inclusive.";

    return "";
  }


  public int[] getExpectation(int[] n, int[] m) {
    int[] ans = new int[n.length];
    int[] ans2 = new int[n.length];

    int[] c = new int[M + 1];
    c[1] = 1;

    int[][] s = new int[M + 1][M + 1];
    s[0][0] = 1;

    for (int i = 1; i <= M; ++i)
      for (int j = 1; j <= M; ++j)
        s[i][j] = add(s[i - 1][j - 1], mul(s[i - 1][j], j));

    int[] f = new int[M + 1];
    f[0] = 1;
    for (int i = 1; i <= M; ++i)
      f[i] = mul(i, f[i - 1]);


    for (int i = 1; i <= N; ++i) {

      /*
      for (int k = 0; k < n.length; ++k)
        if (n[k] == i) {
          for (int j = 1; j <= n[k]; ++j)
            ans2[k] = add(ans2[k], mul(c[j], pow(j, m[k])));
        }
      */

      for (int j = M; j >= 1; --j)
        c[j] = add(c[j - 1], mul(c[j], i));

      for (int k = 0; k < n.length; ++k)
        if (n[k] == i) {
          for (int j = 0; j <= m[k]; ++j)
            ans[k] = add(ans[k], mul(mul(f[j], s[m[k]][j]), c[j + 1]));
        }
    }

    /*
    for (int k = 0; k < n.length; ++k)
      if (ans[k] != ans2[k]) {
        System.out.print("Wrong: ");
        System.out.println(ans[k]);
        System.out.print("Correct: ");
        System.out.print(ans2[k]);
        System.out.println();
      }
    */

    return ans;
  }

  public static void main(String[] args) {
    CyclesNumber solver = new CyclesNumber();
    int[] n = {3, 20, 30};
    int[] m = {0, 20, 30};
    for (int x : solver.getExpectation(n, m))
      System.out.println(x);
  }

};