# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1216752 | horka | Kangaroo (CEOI16_kangaroo) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD=1e9+7;
int dp[41][41][41][2];
signed main()
{
// ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n; cin>>n;
int st,veg; cin>>st>>veg;
for(int i=1; i<=n; i++)
{
if(i==st || i==veg) continue;
dp[n-1][(i<st?i:i-1)][(st<veg?veg-1:veg)][(i<st?0:1)]=1;
}
if(n==2)
{
cout<<"1\n";
return;
}
for(int i=n-1; i>1; i--)
{
for(int curr=1; curr<=i; curr++)
for(int v=1; v<=i; v++)
for(int last=0; last<2; last++)
{
if(dp[i][curr][v][last]==0) continue;
if(last==1)
{
for(int kov=1; kov<curr; kov++)
dp[i-1][kov][(curr<v?v-1:v)][0]=(dp[i-1][kov][(curr<v?v-1:v)][0]+dp[i][curr][v][last])%MOD;
}
else
{
for(int kov=curr+1; kov<=i; kov++){
//if(i==2 && curr==1 && v==2 && last==0) cout<<"itt: "<<dp[i][curr][v][last]<<" "<<kov<<endl;
dp[i-1][kov-1][(curr<v?v-1:v)][1]=(dp[i-1][kov-1][(curr<v?v-1:v)][1]+dp[i][curr][v][last])%MOD;}
}
}
}
// cout<<dp[2][1][2][0]<<endl;
//5
//cout<<dp[2][2][1][1]<<endl;
//cout<<dp[2][1][2][0]<<endl;
cout<<(dp[1][1][1][0]+dp[1][1][1][1])%MOD<<"\n";
}