Submission #14770926

---

Source Code Expand

// dfmt off
T lread(T=long)(){return readln.chomp.to!T;}T[] lreads(T=long)(long n){return iota(n).map!((_)=>lread!T).array;}
T[] aryread(T=long)(){return readln.split.to!(T[]);}void arywrite(T)(T a){a.map!text.join(' ').writeln;}
void scan(L...)(ref L A){auto l=readln.split;foreach(i,T;L){A[i]=l[i].to!T;}}alias sread=()=>readln.chomp();
void dprint(L...)(lazy L A){debug{auto l=new string[](L.length);static foreach(i,a;A)l[i]=a.text;arywrite(l);}}
static immutable MOD=10^^9+7;alias PQueue(T,alias l="b<a")=BinaryHeap!(Array!T,l);import std;
// dfmt on

/// x^^n % m
long powmod(long x, long n)
{
    alias T = long;
    T m = 10 ^^ 9 + 7;
    if (n < 1)
        return 1;
    if (n & 1)
    {
        return x * powmod(x, n - 1) % m;
    }
    T tmp = powmod(x, n / 2);
    return tmp * tmp % m;
}

long invmod(long x)
{
    return powmod(x, MOD - 2L);
}
// alias invmod = (long x, long m = 10 ^^ 9 + 7) => powmod(x, m - 2, m);

void main()
{
    long N, M;
    scan(N, M);

    auto memo = new long[](M + 1);
    memo[0] = 1;
    foreach (i; 1 .. M + 1)
        memo[i] = memo[i - 1] * i % MOD;
    auto inv = new long[](M + 1);
    foreach (i; 0 .. M + 1)
        inv[i] = invmod(memo[i]);

    long Permutation(long n, long r)
    {
        return memo[n] * inv[n - r] % MOD;
    }

    long Combination(long n, long r)
    {
        return (memo[n] * inv[n - r] % MOD) * inv[r] % MOD;
    }

    long a = Permutation(M, N);
    foreach (i; 1 .. N + 1)
    {
        long b = Permutation(M - i, N - i);
        // dprint(i, a, b, (N - i + 1));
        a += MOD;
        a += (b * Combination(N, i) % MOD) * ((i & 1) ? -1 : 1);
        a %= MOD;
    }
    writeln(a * Permutation(M, N) % MOD);
}

Submission Info

Judge Result