満点の解説です。

\((1,2,\dots,N)\)の順列\(p\)であって\(p_i>p_{i+1}\)なる\(i\)が\(K-1\)個あるものの個数を求める問題です。

便宜上、\(K \leftarrow K-1\)としておきます。

まず、包除原理により答えを立式すると、

\(\displaystyle\sum_{S \subseteq [N-1],|S|=K} \sum_{T \subseteq S} (-1)^{K-|T|} \binom{N}{t_1,t_2-t_1,\dots,N-t_{|T|}}=N! \sum_{T \subseteq [N-1], |T| \leq K} (-1)^{K-|T|} \binom{N-1-|T|}{K-|T|} \frac{1}{t_1!(t_2-t_1)!\cdots(N-t_{|T|})!} \)

です。ここで、\(|T|\)についてまとめると、形式的冪級数を用いて

\(N! \displaystyle\sum_{m=0}^K (-1)^{K-m} \binom{N-1-m}{K-m} [x^N] (\exp(x)-1)^{m+1} = \sum_{m=0}^K (-1)^{K-m} \binom{N-1-m}{K-m} \sum_{l=0}^{m+1} (-1)^{m+1-l} \binom{m+1}{l} l^N\)

となります。この右辺の\(2\)つの\(\displaystyle\sum\)を交換すると、

\(\displaystyle\sum_{l=0}^{K+1} (-1)^{K+1-l} l^N \sum_{m=0}^{K} \binom{N-1-m}{K-m} \binom{m+1}{l}=\displaystyle\sum_{l=0}^{K+1} (-1)^{K+1-l} l^N \sum_{m=0}^{K} \binom{N-1-m}{N-1-K} \binom{m+1}{l}\)

となり、\(\displaystyle\sum_{m=0}^{K} \binom{N-1-m}{N-1-K} \binom{m+1}{l}\)は\(\displaystyle[x^{K+1-l}]\frac{1}{(1-x)^{N-K}} \times \frac{1}{(1-x)^{l+1}}=\binom{N+1}{K+1-l}\)と等しいので、答えは

\(\displaystyle\sum_{l=0}^{K+1} (-1)^{K+1-l} l^N \binom{N+1}{K+1-l}\)

です。これは、累乗の計算に繰り返し二乗法を用い、フェルマーの小定理を利用して階乗およびその逆元を前計算しておけば\(O(N \log N + \log mod)\)時間で解けます。なお、線形篩を利用すれば\(O(N + \log mod)\)時間を達成することができます。

解答例(C++)

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll mod=1000000007;
ll modpow(ll a,ll n){
    ll ret=1;
    while(n){
        if(n&1) ret=(ret*a)%mod;
        a=(a*a)%mod;
        n>>=1;
    }
    return ret;
}
ll modinv(ll a){
    return modpow(a,mod-2);
}
int main(){
    int n,k;
    cin>>n>>k;
    k--;
    vector<ll> fact(n+2),rfact(n+2);
    fact[0]=1;
    for(int i=0;i<=n;i++) fact[i+1]=(fact[i]*(i+1))%mod;
    rfact[n+1]=modinv(fact[n+1]);
    for(int i=n+1;i>0;i--) rfact[i-1]=(rfact[i]*i)%mod;
    auto bin=[&](int a,int b)->ll{
        return (((fact[a]*rfact[b])%mod)*rfact[a-b])%mod;
    };
    ll ans=0;
    for(int l=0;l<=k+1;l++){
        if((k+1-l)&1) ans-=(bin(n+1,k-l+1)*modpow(l,n))%mod;
        else ans+=(bin(n+1,k-l+1)*modpow(l,n))%mod;
        ans+=mod;
        ans%=mod;
    }
    cout<<ans<<'\n';
}