#include #include #include #include #include #include #include #include #include #include #include #include #include #include //#include #include #include #include #include #include #define FOR(i,a,b) for (ll i=(a);i<(ll)(b);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() #define SUM(v) accumulate(ALL(v),0ll) using ll = long long; const ll INF=10e10; const ll eps=1; const double pi=3.14159265359; const ll mod=10000000000+7; using namespace std; //Union Find テンプレ struct UnionFind { vector par , siz; UnionFind(int n) : par(n,-1) , siz(n,1) { } int root(int x) { if(par[x] == -1) return x; else return par[x] = root(par[x]); } bool issame(int x, int y) { return root(x) == root(y); } bool unite(int x, int y) { x = root(x) ; y = root(y); if(x == y) return false; if(siz[x] < siz[y]) swap(x,y); par[y] = x; siz[x] += siz[y]; return true; } int size(int x) { return siz[root(x)]; } }; ll k; vector dp(k+5); string s; int main() { cin>>k; if(k==1) { cout<<1<