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_3 {
        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[] lpf = enumLowestPrimeFactors(n);
                long[] ps = enumPowsUnderConstE(n-1, n, lpf, mod);
                
                int[][] fif = enumFIF(Z, mod);
                long ans = 0;
                long big = 8L*mod*mod;
                for(int j = 0;j < n;j++){
                        ans += der[j] * fif[1][j] % mod * fif[1][n-1-j] % mod * ps[n-j];
                        if(ans >= big)ans -= big;
                }
                ans %= mod;
                out.println(ans);
        }
        
        
        
        static long[] enumPowsUnderConstE(int e, int n, int[] lpf, int mod)
        {
                long[] ret = new long[n+1];
                for(int i = 1;i <= n;i++){
                        if(i == lpf[i] || i == 1){
                                ret[i] = pow(i, e, mod);
                        }else{
                                ret[i] = ret[i/lpf[i]] * ret[lpf[i]] % mod;
                        }
                }
                return ret;
        }
        
        public static int[] enumLowestPrimeFactors(int n) {
                int tot = 0;
                int[] lpf = new int[n + 1];
                int u = n + 32;
                double lu = Math.log(u);
                int[] primes = new int[(int) (u / lu + u / lu / lu * 1.5)];
                for (int i = 2; i <= n; i++)
                        lpf[i] = i;
                for (int p = 2; p <= n; p++) {
                        if (lpf[p] == p)
                                primes[tot++] = p;
                        int tmp;
                        for (int i = 0; i < tot && primes[i] <= lpf[p] && (tmp = primes[i] * p) <= n; i++) {
                                lpf[tmp] = primes[i];
                        }
                }
                return lpf;
        }

        
        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_3().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));
        }
}
# ユーザ名 問題 言語 状態 得点 提出日時
00276 uwi 0014 - ベル数 Java8 AC 100 18-03-23 14:19

セット

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

テストケース

テストケース取得

ファイル名 状態 実行時間 メモリ使用量 #
test-full-11.txt AC 190 ms 25900 KB 1
test-full-12.txt AC 220 ms 26548 KB 1
test-full-13.txt AC 170 ms 24280 KB 1
test-full-14.txt AC 210 ms 25856 KB 1
test-full-15.txt AC 220 ms 24288 KB 1
test-partial-1.txt AC 120 ms 21888 KB 1 2
test-partial-10.txt AC 140 ms 24064 KB 1 2
test-partial-2.txt AC 160 ms 22532 KB 1 2
test-partial-3.txt AC 150 ms 23348 KB 1 2
test-partial-4.txt AC 170 ms 23104 KB 1 2
test-partial-5.txt AC 120 ms 22888 KB 1 2
test-partial-6.txt AC 140 ms 23968 KB 1 2
test-partial-7.txt AC 120 ms 23940 KB 1 2
test-partial-8.txt AC 150 ms 23780 KB 1 2
test-partial-9.txt AC 120 ms 23012 KB 1 2