# Phoenix and Computers solution codeforces – There are nn computers in a row, all originally off, 2021

## Phoenix and Computers solution codeforces

Phoenix and Computers solution codeforces Phoenix and Computers solution codeforces Phoenix and Computers solution codeforces

There are nn computers in a row, all originally off, and Phoenix wants to turn all of them on. He will manually turn on computers one at a time. At any point, if computer i1i−1 and computer i+1i+1 are both on, computer ii (2in1)(2≤i≤n−1) will turn on automatically if it is not already on. Note that Phoenix cannot manually turn on a computer that already turned on automatically.

If we only consider the sequence of computers that Phoenix turns on manually, how many ways can he turn on all the computers? Two sequences are distinct if either the set of computers turned on manually is distinct, or the order of computers turned on manually is distinct. Since this number may be large, please print it modulo MM.

Input Phoenix and Computers solution codeforces

The first line contains two integers nn and MM (3n4003≤n≤400108M109108≤M≤109) — the number of computers and the modulo. It is guaranteed that MM is prime.

Output Phoenix and Computers solution codeforces

Print one integer — the number of ways to turn on the computers modulo MM.

Examples Phoenix and Computers solution codeforces

input Phoenix and Computers solution codeforces

Copy
3 100000007


output

Copy
6


input

Copy
4 100000007


output

Copy
20


input

Copy
400 234567899


output

Copy
20914007

Note

In the first example, these are the 66 orders in which Phoenix can turn on all computers:

• [1,3][1,3]. Turn on computer 11, then 33. Note that computer 22 turns on automatically after computer 33 is turned on manually, but we only consider the sequence of computers that are turned on manually.
• [3,1][3,1]. Turn on computer 33, then 11.
• [1,2,3][1,2,3]. Turn on computer 1122, then 33.
• [2,1,3][2,1,3]
• [2,3,1][2,3,1]
• [3,2,1]

# C++

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {
int t=1;
//cin>>t;
while(t--)
{
long long n,m,ans=0;
cin>>n>>m;
n+=1;
long long f[4444]={0};
f[0]=1;
for(int i=1;i<=n/2;i++)
{
for(int j=0;j<=n-i*2;j++)
{
f[j]=(f[j] + (j ? f[j - 1] * 2 : 0)) * i % m;
//cout<<f[j]<<" ";
}
ans=(ans+f[n-i*2])%m;
}
cout<<ans<<"\n";

}
return 0;
}



## FPC

var f:array[0..400,0..400]of int64;
pw:array[0..400]of int64;
c:array[-10..400,-10..400]of int64;
n,m,s:int64;i,j,k:longint;
begin
f[1,1]:=1;f[2,1]:=2;
pw[0]:=1;
c[1,0]:=1;c[1,1]:=1;
for i:=2 to n do
for j:=0 to n do
c[i,j]:=(c[i-1,j]+c[i-1,j-1]) mod m;
for i:=1 to n do
pw[i]:=(pw[i-1]*2)mod m;
for i:=3 to n do
for j:=1 to (i+1)>>1 do
begin
if j<>1 then
for k:=1 to i-2 do
f[i,j]:=(f[i,j]+f[k,j-1]*c[i-j+1,i-k-1]mod m*pw[i-k-2]mod m)mod m
else
f[i,j]:=pw[i-1];
if i=n then s:=(s+f[i,j])mod m;
end;
writeln(s);
end.

## JAVA 11

import java.io.*;
import java.util.*;

public class CF1515E extends PrintWriter {
CF1515E() { super(System.out, true); }
Scanner sc = new Scanner(System.in);
public static void main(String[] \$) {
CF1515E o = new CF1515E(); o.main(); o.flush();
}

void main() {
int n = sc.nextInt();
int md = sc.nextInt();
int k = (n + 1) / 2;
int[][] dp = new int[k + 1][n + 1]; dp[0][0] = 1;
for (int h = 1; h <= k; h++)
for (int l = h; l <= n - h + 1; l++)
dp[h][l] = (int) ((dp[h][l - 1] * 2L + dp[h - 1][l - 1]) * h % md);
int ans = 0;
for (int h = 1; h <= k; h++)
ans = (ans + dp[h][n - h + 1]) % md;
println(ans);
}
}

## PyPy 3

def getc():
f = [[0]*500 for i in range(500)]
for i in range(500):
f[i][0] = 1
f[1][0] = 1
f[1][1] = 1
for i in range(2,411):
for j in range(1, i+1):
f[i][j] = (f[i-1][j-1] + f[i-1][j])%mod
return f
n, mod = map(int, input().split())
f = [[0]*500 for i in range(500)]
c = getc()
mi_2 = [0]*500
mi_2[0] = 1
for i in range(1, 500):
mi_2[i] = mi_2[i-1]*2%mod
for i in range(1, n+1):
for j in range(0, i//2+1):
if j == 0:
f[i][j] = mi_2[i-1]
else:
for k in range(2, i):
f[i][j] = (f[i][j] + ((mi_2[k-2]*f[i-k][j-1])%mod)*c[i-j][k-1]%mod)%mod
ans = 0
for i in range(0,n+1):
ans = (ans + f[n][i])%mod
print(ans)

## PyPy 3 (sol 2)

from __pypy__.intop import int_mulmod

n_, MOD = [int(t) for t in input().split()]

def mul(a, b):
return int_mulmod(a, b, MOD)

N = 410
dp = [[0] * (N+1) for _ in range(N+1)]

fact = [1]
for x in range(1, N):
fact.append(fact[-1] * x % MOD)

inv_fact = [0] * N
inv_fact[-1] = pow(fact[-1], MOD - 2, MOD)
for x in reversed(range(1, N)):
inv_fact[x - 1] = inv_fact[x] * x % MOD

def nCr(n, r):
return mul(fact[n], mul(inv_fact[n-r], inv_fact[r]))

for n in range(1, N+1):
dp[n][n] = pow(2, n-1, MOD)
for i in range(1, n-1):
j = n-i-1
for k in range(1, i+1):
dp[n][k+j] = (dp[n][k+j]
+ mul(nCr(k+j, k), mul(dp[i][k], dp[j][j]))) % MOD

print(sum(dp[n_]) % MOD)