#include <bits/stdc++.h>
      
#define FOR(i,a,b) for( ll i = (a); i < (ll)(b); i++ )
#define REP(i,n) FOR(i,0,n)
#define YYS(x,arr) for(auto& x:arr)
#define ALL(x) (x).begin(),(x).end()
#define SORT(x) sort( (x).begin(),(x).end() )
#define REVERSE(x) reverse( (x).begin(),(x).end() )
#define UNIQUE(x) (x).erase( unique( ALL( (x) ) ) , (x).end() )
#define PW(x) (1LL<<(x))
#define SZ(x) ((ll)(x).size())
#define SHOW(x) cout << #x << " = " << x << endl
#define SHOWA(x,n) for( int yui = 0; yui < n; yui++ ){ cout << x[yui] << " "; } cout << endl

#define pb emplace_back
#define fi first
#define se second

using namespace std;

typedef long double ld;
typedef long long int ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<ld> vd;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<vpl> gr;
typedef vector<vl> ml;
typedef vector<vd> md;
typedef vector<vi> mi;
     
const ll INF = (ll)1e9 + 10;
const ll INFLL = (ll)1e18 + 10;
const ld EPS = 1e-12;
const ll MOD = 1e9+7;
     
template<class T> T &chmin( T &a , const T &b ){ return a = min(a,b); }
template<class T> T &chmax( T &a , const T &b ){ return a = max(a,b); }
template<class T> inline T sq( T a ){ return a * a; }

ll in(){ long long int x; scanf( "%lld" , &x ); return x; }
char yuyushiki[1000010]; string stin(){ scanf( "%s" , yuyushiki ); return yuyushiki; }

// head


struct Mod{
  unsigned n;
  Mod() : n(0){}
  Mod( ll x ){
    if( x < 0 ) n = x%MOD+MOD;
    else n = x%MOD;
  }
};
Mod operator + ( Mod a  , Mod b ){ return Mod( a.n + b.n ); }
Mod operator +=( Mod &a , Mod b ){ return a = a + b; }
Mod operator - ( Mod a ){ return Mod( MOD - a.n ); }
Mod operator - ( Mod a  , Mod b ){ return Mod( a.n + MOD - b.n ); }
Mod operator -=( Mod &a , Mod b ){ return a = a - b; }
Mod operator * ( Mod a  , Mod b ){ return Mod( (ll)a.n * b.n ); }
Mod operator *=( Mod &a , Mod b ){ return a = a * b; }
Mod modpow( Mod x , ll k ){
  Mod res = 1;
  while( k ){
    if( k & 1 ) res *= x;
    k /= 2;
    x *= x;
  }
  return res;
}
ll extgcd( ll a , ll b , ll &x , ll &y ){
  ll d = a;
  if( b != 0 ){
    d = extgcd( b , a % b , y , x );
    y -= a / b * x;
  } else {
    x = 1, y = 0;
  }
  return d;
}
Mod inv( Mod a ){ ll x, y; assert( extgcd( a.n , MOD , x , y ) == 1 ); return Mod( x ); }
Mod operator / ( Mod a  , Mod b ){ return Mod( (ll)a.n * inv(b).n ); }
Mod operator /=( Mod &a , Mod b ){ return a = a / b; }

Mod dp[110][10010];
bool used[110][10010];

Mod cnt[110];

int n, k;

Mod rec( int p , int w ){
  if( used[p][w] ){
    return dp[p][w];
  }
  used[p][w] = true;
  if( p == 1 ){
    Mod res = 0;
    FOR( i , 2 , k+1 ){
      res += i + w;
    }
    return dp[p][w] = res;
  }
  Mod res = 0;  
  REP( i , k+1 ){
    if( i <= p ){
      /*
      if( p == 3)
        cout << (cnt[p-1] * ((w+i) % p)).n << " " << (w+i) / p << " " << (rec(p-1, (w+i) / p)).n << endl;
      */
      res += cnt[p-1] * ((w+i) % p) + rec(p-1, (w+i) / p + w);
    } else {
      res += cnt[p-1] * (w+i) + rec(p-1, w);
    }
  }
  return dp[p][w] = res;
}

int main(){

  n = in();
  k = in();

  REP( i , n+1 ){
    cnt[i] = modpow(k + 1, i);
  }

  printf( "%d\n", (int)rec( n , 0 ).n );
  return 0;

  ll ans = 0;

  ll an[4] = {};
  REP( i , k+1 ){
    REP( j , k+1 ){
      REP( l , k+1 ){
        ll a[3] = { i , j , l };
        bool update = true;
        while( update ){
          update = false;
          REP( s , 3 ){
            if( a[s] == s + 1 ){
              a[s] = 0;
              REP( t , s ){
                a[t]++;
              }
              update = true;
              break;
            }
          }
        }
        REP( s , 3 ){
          ans += a[s];
          an[l] += a[s];
        }
      }
    }
  }

  cout << ans << endl;
  REP( i , 4 ){
    cout << an[i] << " ";
  }
  cout << endl;
  
  return 0;
}

### Prompt

Your task is to create a Cpp solution to the following problem:

Consider the following game:

* The game is played using a row of N squares and many stones.
* First, a_i stones are put in Square i\ (1 \leq i \leq N).
* A player can perform the following operation as many time as desired: "Select an integer i such that Square i contains exactly i stones. Remove all the stones from Square i, and add one stone to each of the i-1 squares from Square 1 to Square i-1."
* The final score of the player is the total number of the stones remaining in the squares.



For a sequence a of length N, let f(a) be the minimum score that can be obtained when the game is played on a.

Find the sum of f(a) over all sequences a of length N where each element is between 0 and K (inclusive). Since it can be extremely large, find the answer modulo 1000000007 (= 10^9+7).

Constraints

* 1 \leq N \leq 100
* 1 \leq K \leq N

Input

Input is given from Standard Input in the following format:


N K


Output

Print the sum of f(a) modulo 1000000007 (= 10^9+7).

Examples

Input

2 2


Output

10


Input

20 17


Output

983853488

### Response

```cpp
#include <bits/stdc++.h>
      
#define FOR(i,a,b) for( ll i = (a); i < (ll)(b); i++ )
#define REP(i,n) FOR(i,0,n)
#define YYS(x,arr) for(auto& x:arr)
#define ALL(x) (x).begin(),(x).end()
#define SORT(x) sort( (x).begin(),(x).end() )
#define REVERSE(x) reverse( (x).begin(),(x).end() )
#define UNIQUE(x) (x).erase( unique( ALL( (x) ) ) , (x).end() )
#define PW(x) (1LL<<(x))
#define SZ(x) ((ll)(x).size())
#define SHOW(x) cout << #x << " = " << x << endl
#define SHOWA(x,n) for( int yui = 0; yui < n; yui++ ){ cout << x[yui] << " "; } cout << endl

#define pb emplace_back
#define fi first
#define se second

using namespace std;

typedef long double ld;
typedef long long int ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<ld> vd;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<vpl> gr;
typedef vector<vl> ml;
typedef vector<vd> md;
typedef vector<vi> mi;
     
const ll INF = (ll)1e9 + 10;
const ll INFLL = (ll)1e18 + 10;
const ld EPS = 1e-12;
const ll MOD = 1e9+7;
     
template<class T> T &chmin( T &a , const T &b ){ return a = min(a,b); }
template<class T> T &chmax( T &a , const T &b ){ return a = max(a,b); }
template<class T> inline T sq( T a ){ return a * a; }

ll in(){ long long int x; scanf( "%lld" , &x ); return x; }
char yuyushiki[1000010]; string stin(){ scanf( "%s" , yuyushiki ); return yuyushiki; }

// head


struct Mod{
  unsigned n;
  Mod() : n(0){}
  Mod( ll x ){
    if( x < 0 ) n = x%MOD+MOD;
    else n = x%MOD;
  }
};
Mod operator + ( Mod a  , Mod b ){ return Mod( a.n + b.n ); }
Mod operator +=( Mod &a , Mod b ){ return a = a + b; }
Mod operator - ( Mod a ){ return Mod( MOD - a.n ); }
Mod operator - ( Mod a  , Mod b ){ return Mod( a.n + MOD - b.n ); }
Mod operator -=( Mod &a , Mod b ){ return a = a - b; }
Mod operator * ( Mod a  , Mod b ){ return Mod( (ll)a.n * b.n ); }
Mod operator *=( Mod &a , Mod b ){ return a = a * b; }
Mod modpow( Mod x , ll k ){
  Mod res = 1;
  while( k ){
    if( k & 1 ) res *= x;
    k /= 2;
    x *= x;
  }
  return res;
}
ll extgcd( ll a , ll b , ll &x , ll &y ){
  ll d = a;
  if( b != 0 ){
    d = extgcd( b , a % b , y , x );
    y -= a / b * x;
  } else {
    x = 1, y = 0;
  }
  return d;
}
Mod inv( Mod a ){ ll x, y; assert( extgcd( a.n , MOD , x , y ) == 1 ); return Mod( x ); }
Mod operator / ( Mod a  , Mod b ){ return Mod( (ll)a.n * inv(b).n ); }
Mod operator /=( Mod &a , Mod b ){ return a = a / b; }

Mod dp[110][10010];
bool used[110][10010];

Mod cnt[110];

int n, k;

Mod rec( int p , int w ){
  if( used[p][w] ){
    return dp[p][w];
  }
  used[p][w] = true;
  if( p == 1 ){
    Mod res = 0;
    FOR( i , 2 , k+1 ){
      res += i + w;
    }
    return dp[p][w] = res;
  }
  Mod res = 0;  
  REP( i , k+1 ){
    if( i <= p ){
      /*
      if( p == 3)
        cout << (cnt[p-1] * ((w+i) % p)).n << " " << (w+i) / p << " " << (rec(p-1, (w+i) / p)).n << endl;
      */
      res += cnt[p-1] * ((w+i) % p) + rec(p-1, (w+i) / p + w);
    } else {
      res += cnt[p-1] * (w+i) + rec(p-1, w);
    }
  }
  return dp[p][w] = res;
}

int main(){

  n = in();
  k = in();

  REP( i , n+1 ){
    cnt[i] = modpow(k + 1, i);
  }

  printf( "%d\n", (int)rec( n , 0 ).n );
  return 0;

  ll ans = 0;

  ll an[4] = {};
  REP( i , k+1 ){
    REP( j , k+1 ){
      REP( l , k+1 ){
        ll a[3] = { i , j , l };
        bool update = true;
        while( update ){
          update = false;
          REP( s , 3 ){
            if( a[s] == s + 1 ){
              a[s] = 0;
              REP( t , s ){
                a[t]++;
              }
              update = true;
              break;
            }
          }
        }
        REP( s , 3 ){
          ans += a[s];
          an[l] += a[s];
        }
      }
    }
  }

  cout << ans << endl;
  REP( i , 4 ){
    cout << an[i] << " ";
  }
  cout << endl;
  
  return 0;
}

```