1616 Baile de Formatura

#include<bits/stdc++.h>
using namespace std ;
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int mod = 1e9 + 7;

int B, G;
int dp[1005][1005];
int seen[1005][1005];
int timestamp = 1;

int ways(int n, int m) {
    if(m < 0) {
        return 0;
    }
    if(n == 0) {
        if(m == 0) {
            return 1;
        }
        return 0;
    }
    if(seen[n][m] == timestamp) {
        return dp[n][m];
    }
    int ans1 = (ways(n - 1, m - 1) * 1ll * m) % mod;
    int ans2 = (ways(n - 1, m) * 1ll * (G - m)) % mod;
    seen[n][m] = timestamp;
    return dp[n][m] = (ans1 + ans2) % mod;
}

int main(){

    ios_base::sync_with_stdio(false) ; cin.tie(NULL) ;

    while(cin >> B >> G and B and G) {
        ++timestamp;
        cout << ways(B, G) << '\n';
    }

    return 0;
}