Submission #938756

#TimeUsernameProblemLanguageResultExecution timeMemory
938756Doncho_BonbonchoKangaroo (CEOI16_kangaroo)C++17
100 / 100
13 ms32348 KiB
#include <bits/stdc++.h>
using namespace std;

template< class T, class T2 > inline bool chkmin( T& a, const T2& b ){ return a > b ? a = b, 1 : 0; }
template< class T, class T2 > inline bool chkmax( T& a, const T2& b ){ return a < b ? a = b, 1 : 0; }

#ifndef LOCAL
#define cerr if( false )cerr
#endif

#define out(x) #x << " = " << x << "  "

typedef long long ll;

const int MAX_N = 2048;
const ll mod = 1e9 + 7;

ll dp[MAX_N][MAX_N];

int main (){

#ifndef LOCAL
	std::ios_base::sync_with_stdio( false ); std::cin.tie( NULL ); std::cout.tie( NULL );
#endif

	int n, S, E;
	std::cin >> n >> S >> E;

	dp[1][1] = 1;
	for( int i=2 ; i <= n ; i++ ){
		for( int j=1 ; j <= i ; j ++ ){
			if( i == S || i == E ){
				dp[i][j] = ( dp[i-1][j-1] + dp[i-1][j] ) % mod;
			}else{
				dp[i][j] = ( dp[i-1][j+1] * j ) % mod;
				dp[i][j] += ( dp[i-1][j-1] * ( j - ( S < i ) - ( E < i ) ) ) %mod;
				if( dp[i][j] >= mod ) dp[i][j] -= mod;
			}
		}
	}
	
	std::cout << dp[n][1] << endl;
	
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...