raw source code
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

class N14 {
        InputStream is;
        PrintWriter out;
        String INPUT = "";

        void solve() {
                int Z = 100005;
                int mod = 1000000007;
                
                int n = ni();
                if(n == 0){
                        out.println(1);
                        return;
                }
                
                long[] der = new long[Z];
                der[0] = 1;
                for(int i = 2;i < Z;i++){
                        der[i] = (der[i-1] + der[i-2]) * (i-1) % mod;
                }
                
                int[][] fif = enumFIF(Z, mod);
                long ans = 0;
                for(int j = 0;j < n;j++){
                        ans += der[j] * C(n-1, j, mod, fif) % mod * pow(n-j, n-1, mod);
                        ans %= mod;
                }
                ans = ans * fif[1][n-1] % mod;
                out.println(ans);
        }
        
        public static long pow(long a, long n, long mod) {
                //                a %= mod;
                long ret = 1;
                int x = 63 - Long.numberOfLeadingZeros(n);
                for (; x >= 0; x--) {
                        ret = ret * ret % mod;
                        if (n << 63 - x < 0)
                                ret = ret * a % mod;
                }
                return ret;
        }

        
        public static long C(int n, int r, int mod, int[][] fif) {
                if (n < 0 || r < 0 || r > n)
                        return 0;
                return (long) fif[0][n] * fif[1][r] % mod * fif[1][n - r] % mod;
        }
        
        public static int[][] enumFIF(int n, int mod) {
                int[] f = new int[n + 1];
                int[] invf = new int[n + 1];
                f[0] = 1;
                for (int i = 1; i <= n; i++) {
                        f[i] = (int) ((long) f[i - 1] * i % mod);
                }
                long a = f[n];
                long b = mod;
                long p = 1, q = 0;
                while (b > 0) {
                        long c = a / b;
                        long d;
                        d = a;
                        a = b;
                        b = d % b;
                        d = p;
                        p = q;
                        q = d - c * q;
                }
                invf[n] = (int) (p < 0 ? p + mod : p);
                for (int i = n - 1; i >= 0; i--) {
                        invf[i] = (int) ((long) invf[i + 1] * (i + 1) % mod);
                }
                return new int[][] { f, invf };
        }


        void run() throws Exception {
                is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
                out = new PrintWriter(System.out);

                long s = System.currentTimeMillis();
                solve();
                out.flush();
                if (!INPUT.isEmpty())
                        tr(System.currentTimeMillis() - s + "ms");
        }

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

        private byte[] inbuf = new byte[1024];
        public int lenbuf = 0, ptrbuf = 0;

        private int readByte() {
                if (lenbuf == -1)
                        throw new InputMismatchException();
                if (ptrbuf >= lenbuf) {
                        ptrbuf = 0;
                        try {
                                lenbuf = is.read(inbuf);
                        } catch (IOException e) {
                                throw new InputMismatchException();
                        }
                        if (lenbuf <= 0)
                                return -1;
                }
                return inbuf[ptrbuf++];
        }

        private boolean isSpaceChar(int c) {
                return !(c >= 33 && c <= 126);
        }

        private int skip() {
                int b;
                while ((b = readByte()) != -1 && isSpaceChar(b))
                        ;
                return b;
        }

        private double nd() {
                return Double.parseDouble(ns());
        }

        private char nc() {
                return (char) skip();
        }

        private String ns() {
                int b = skip();
                StringBuilder sb = new StringBuilder();
                while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != '
                                                                        // ')
                        sb.appendCodePoint(b);
                        b = readByte();
                }
                return sb.toString();
        }

        private char[] ns(int n) {
                char[] buf = new char[n];
                int b = skip(), p = 0;
                while (p < n && !(isSpaceChar(b))) {
                        buf[p++] = (char) b;
                        b = readByte();
                }
                return n == p ? buf : Arrays.copyOf(buf, p);
        }

        private char[][] nm(int n, int m) {
                char[][] map = new char[n][];
                for (int i = 0; i < n; i++)
                        map[i] = ns(m);
                return map;
        }

        private int[] na(int n) {
                int[] a = new int[n];
                for (int i = 0; i < n; i++)
                        a[i] = ni();
                return a;
        }

        private int ni() {
                int num = 0, b;
                boolean minus = false;
                while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
                        ;
                if (b == '-') {
                        minus = true;
                        b = readByte();
                }

                while (true) {
                        if (b >= '0' && b <= '9') {
                                num = num * 10 + (b - '0');
                        } else {
                                return minus ? -num : num;
                        }
                        b = readByte();
                }
        }

        private long nl() {
                long num = 0;
                int b;
                boolean minus = false;
                while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
                        ;
                if (b == '-') {
                        minus = true;
                        b = readByte();
                }

                while (true) {
                        if (b >= '0' && b <= '9') {
                                num = num * 10 + (b - '0');
                        } else {
                                return minus ? -num : num;
                        }
                        b = readByte();
                }
        }

        private static void tr(Object... o) {
                System.out.println(Arrays.deepToString(o));
        }
}
# ユーザ名 問題 言語 状態 得点 提出日時
00270 uwi 0014 - ベル数 Java8 AC 100 18-03-23 01:55

セット

# セット 得点 Cases
1 ALL 50 / 50 *
2 partial 50 / 50 test-partial-*.txt

テストケース

テストケース取得

ファイル名 状態 実行時間 メモリ使用量 #
test-full-11.txt AC 270 ms 22764 KB 1
test-full-12.txt AC 210 ms 23756 KB 1
test-full-13.txt AC 220 ms 23312 KB 1
test-full-14.txt AC 180 ms 22380 KB 1
test-full-15.txt AC 230 ms 23756 KB 1
test-partial-1.txt AC 120 ms 23116 KB 1 2
test-partial-10.txt AC 120 ms 24044 KB 1 2
test-partial-2.txt AC 140 ms 22652 KB 1 2
test-partial-3.txt AC 130 ms 22728 KB 1 2
test-partial-4.txt AC 140 ms 24456 KB 1 2
test-partial-5.txt AC 190 ms 22292 KB 1 2
test-partial-6.txt AC 120 ms 24160 KB 1 2
test-partial-7.txt AC 130 ms 22812 KB 1 2
test-partial-8.txt AC 140 ms 23684 KB 1 2
test-partial-9.txt AC 130 ms 24032 KB 1 2