Language: C++

#include<bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define int long long
#define vec(a,n) vector<int> (a)((n));
#define Vec(a,n) vector<string> (a)((n));
#define twovec(a,n,m) vector<vector<int>> a(n,vector<int>(m,0));
#define Twovec(a,n,m) vector<vector<double>> a(n,vector<double>(m,0));
#define P pair<int,int>
#define All(a) (a).begin(),(a).end()
#define Sort(a) sort(All(a));
#define Reverse(a) reverse(All(a));
#define PQ(n) priority_queue<P,vector<P>,greater<P>> (n)
#define pq(n) priority_queue<int> (n)
#define print(a) cout << (a) << endl
#define printD(a) cout << setprecision(15) << (a) << endl;
using namespace std;
int max_int = 2147483647;
//int prime = 998244353;
int prime = 1e9+7;
void Debug(auto a);
int nibul(auto a,auto b);
int nibuu(auto a,auto b);
void input(vector<auto>& a,int n);
double PI = 3.14159265358979;
int n;
const int limit = 200006;
int fac[limit];
int finv[limit];
int inv[limit];

class m_int{
    public:
    int_fast32_t MOD = prime;
    int_fast32_t d=0;
    m_int(int val=0){
        if (val >= MOD) { val %= MOD; } else if (val < 0) { val %= MOD; val += MOD; }d = val;
    }
    m_int operator =(constexpr m_int x){
        this->d = x.d;
        return *this;
    }
    m_int operator+(const m_int another){
        m_int tmp;
        if(d+another.d>MOD){
            tmp.d = d+another.d-MOD;
            return tmp;
        }
        else{
            tmp.d = d+another.d;
            return tmp;
        }
    }
    m_int operator-(const m_int &another) const{
        m_int tmp;
        if(d-another.d<(int_fast32_t)0){
            tmp.d = d-another.d+MOD;
            return tmp;
        }
        else{
            tmp.d = d-another.d;
            return tmp;
        }
    }
    m_int operator*(const m_int &another) const{
        m_int tmp;
        tmp.d = d*another.d%MOD;
        return tmp;
    }
    m_int operator/(const m_int &another) const{
        m_int tmp;
        tmp.d = d/another.d%MOD;
        return tmp;
    }
    m_int operator+=(const m_int another){
        (*this) = (*this) + another;
        return *this;
    }
    m_int operator-=(const m_int another){
        (*this) = (*this) - another;
        return *this;
    }
    m_int operator*=(const m_int another){
        (*this) = (*this) * another;
        return *this;
    }
    bool operator<(const m_int &another) const{
        return d < another.d;
    }
    bool operator>(const m_int &another) const{
        return d > another.d;
    }
};
ostream& operator<<(std::ostream& os, const m_int& obj){
    // ここでストリームに obj を書き込みます。
    os << obj.d;
    return os;
}
istream& operator>>(std::istream& is, m_int& obj){
    // ここでストリームから obj を読み込みます。
    is >> obj.d;
    if( false ) is.setstate(std::ios::failbit);
    return is;
}

void COMinit(){
    fac[0] = 1,fac[1] = 1;
    finv[0]=1,finv[1] = 1;
    inv[1]=1;
    FOR(i,2,limit){
        fac[i] = fac[i-1]*i%prime;
        inv[i] = (prime-inv[prime%i]*(prime/i))%prime;
        finv[i] = finv[i-1]*inv[i]%prime;
    }
}

m_int factorical(int n){
    if(fac[0] == 0) COMinit();
    m_int ans;
    if(n >= limit){
        ans = 1;
        FOR(i,2,n+1){
            ans *= i;
        }
        return ans;
    }
    else{
        ans = fac[n];
        return ans;
    }
}
m_int comb(int n,int r){
    if(r>n || n < 0 || r < 0) return 0;
    if(fac[0] == 0) COMinit();
    m_int tmp = finv[r] * finv[n-r];
    tmp *= fac[n];
    return tmp;
}

m_int pow(int x,int exp){
    if(exp <= 0) return 1;
    if(exp%2==0){
        m_int d = pow(x,exp/2);
        return d*d;
    }
    else{
        return (m_int)((m_int)x*(m_int)pow(x,exp-1));
    }
}

signed main(){
    int m,k;
    cin >> n >> m >> k;
    m_int ans(0);
    REP(i,k+1){
        m_int tmp = comb(n-1,i);
        tmp *= m;
        tmp *= pow(m-1,n-1-i);
        ans += tmp;
    }
    print(ans);
    return 0;
}

void Debug(auto a){
    cout << "{ ";
    for(auto b: a){
        cout << b << " ";
    }
    cout << "}" << endl;
}
int nibul(auto a,auto b){
    int x = lower_bound(All(a),b) - a.begin();
    //key以上の初めてのitr
    return x;
}
int nibuu(auto a,auto b){
    int x = upper_bound(All(a),b) - a.begin();
    //key以下の最後のitr
    return x-1;
}

void input(vector<auto>& a,int n){
    REP(i,n){
        cin >> a[i];
    }
}



signed main(){
    int n,k;
    cin >> n >> k;
    m_int ans(0);
    FOR(i,k,n+2){
        int mini = i*(i-1)/2;
        int maxi = (n+n-i+1)*i/2;
        ans += maxi-mini+1;
    }
    print(ans);
    //print(prime);

    return 0;
}

void Debug(auto a){
    cout << "{ ";
    for(auto b: a){
        cout << b << " ";
    }
    cout << "}" << endl;
}
int nibul(auto a,auto b){
    int x = lower_bound(All(a),b) - a.begin();
    //key以上の初めてのitr
    return x;
}
int nibuu(auto a,auto b){
    int x = upper_bound(All(a),b) - a.begin();
    //key以下の最後のitr
    return x-1;
}

void input(vector<auto>& a,int n){
    REP(i,n){
        cin >> a[i];
    }
}


Compiler output:
a.cc:21:12: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   21 | void Debug(auto a);
      |            ^~~~
a.cc:22:11: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   22 | int nibul(auto a,auto b);
      |           ^~~~
a.cc:22:18: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   22 | int nibul(auto a,auto b);
      |                  ^~~~
a.cc:23:11: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   23 | int nibuu(auto a,auto b);
      |           ^~~~
a.cc:23:18: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
   23 | int nibuu(auto a,auto b);
      |                  ^~~~
a.cc:24:19: warning: use of 'auto' in template argument only available with '-fconcepts-ts'
   24 | void input(vector<auto>& a,int n);
      |                   ^~~~
a.cc:39:22: error: a parameter cannot be declared 'constexpr'
   39 |     m_int operator =(constexpr m_int x){
      |                      ^~~~~~~~~
a.cc:165:12: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
  165 | void Debug(auto a){
      |            ^~~~
a.cc:172:11: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
  172 | int nibul(auto a,auto b){
      |           ^~~~
a.cc:172:18: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
  172 | int nibul(auto a,auto b){
      |                  ^~~~
a.cc:177:11: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
  177 | int nibuu(auto a,auto b){
      |           ^~~~
a.cc:177:18: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
  177 | int nibuu(auto a,auto b){
      |                  ^~~~
a.cc:183:19: warning: use of 'auto' in template argument only available with '-fconcepts-ts'
  183 | void input(vector<auto>& a,int n){
      |                   ^~~~
a.cc:191:8: error: redefinition of 'int main()'
  191 | signed main(){
      |        ^~~~
a.cc:151:8: note: 'int main()' previously defined here
  151 | signed main(){
      |        ^~~~
a.cc:206:12: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
  206 | void Debug(auto a){
      |            ^~~~
a.cc:206:6: error: redefinition of 'template<class auto:40> void Debug(auto:40)'
  206 | void Debug(auto a){
      |      ^~~~~
a.cc:165:6: note: 'template<class auto:28> void Debug(auto:28)' previously declared here
  165 | void Debug(auto a){
      |      ^~~~~
a.cc:213:11: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
  213 | int nibul(auto a,auto b){
      |           ^~~~
a.cc:213:18: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
  213 | int nibul(auto a,auto b){
      |                  ^~~~
a.cc:213:5: error: redefinition of 'template<class auto:41, class auto:42> long long int nibul(auto:41, auto:42)'
  213 | int nibul(auto a,auto b){
      |     ^~~~~
a.cc:172:5: note: 'template<class auto:29, class auto:30> long long int nibul(auto:29, auto:30)' previously declared here
  172 | int nibul(auto a,auto b){
      |     ^~~~~
a.cc:218:11: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
  218 | int nibuu(auto a,auto b){
      |           ^~~~
a.cc:218:18: warning: use of 'auto' in parameter declaration only available with '-std=c++20' or '-fconcepts'
  218 | int nibuu(auto a,auto b){
      |                  ^~~~
a.cc:218:5: error: redefinition of 'template<class auto:43, class auto:44> long long int nibuu(auto:43, auto:44)'
  218 | int nibuu(auto a,auto b){
      |     ^~~~~
a.cc:177:5: note: 'template<class auto:31, class auto:32> long long int nibuu(auto:31, auto:32)' previously declared here
  177 | int nibuu(auto a,auto b){
      |     ^~~~~
a.cc:224:19: warning: use of 'auto' in template argument only available with '-fconcepts-ts'
  224 | void input(vector<auto>& a,int n){
      |                   ^~~~
a.cc:224:6: error: redefinition of 'template<class auto:45> void input(std::vector<_Tp>&, long long int)'
  224 | void input(vector<auto>& a,int n){
      |      ^~~~~
a.cc:183:6: note: 'template<class auto:33> void input(std::vector<_Tp>&, long long int)' previously declared here
  183 | void input(vector<auto>& a,int n){
      |      ^~~~~