// O(N^2 2^N) Times. #include using namespace std; using ll=long long; // マクロの定義 #define all(x) x.begin(), x.end() #define len(x) ll(x.size()) #define elif else if #define unless(cond) if (!(cond)) // オーバーロードマクロ #define overload2(_1, _2, name, ...) name #define overload3(_1, _2, _3, name, ...) name #define overload4(_1, _2, _3, _4, name, ...) name #define overload5(_1, _2, _3, _4, _5, name, ...) name // 繰り返し系 #define rep1(n) for (ll i=0; i T floor(T x, U y){return (x>0 ? x/y: (x-y+1)/y);} template T ceil(T x, U y){return (x>0 ? (x+y-1)/y: x/y);} template T mod(T x, U y){ T q=floor(x,y); return x-q*y; } template pair divmod(T x, U y){ T q=floor(x,y); return {q,x-q*y}; } // 指数に関する関数 ll intpow(ll x, ll y){ ll a=1; while (y){ if (y&1) a*=x; x*=x; y>>=1; } return a; } ll modpow(ll x, ll y, ll z){ ll a=1; while (y){ if (y&1) (a*=x)%=z; (x*=x)%=z; y>>=1; } return a; } ll sum(vector &X){ ll y=0; for (auto &&x: X) y+=x; return y; } template T sum(vector &X){ T y=T(0); for (auto &&x: X) y+=x; return y; } // max, min template inline bool chmax(T &a, const U b){ return (a inline bool chmin(T &a, const U b){ return (a>b ? a=b, 1: 0); } template constexpr auto max(T... a){ return max(initializer_list>{a...}); } template constexpr auto min(T... a){ return min(initializer_list>{a...}); } template T max(vector X){ T alpha=X[0]; for (auto x:X) chmax(alpha, x); return alpha; } template T min(vector X){ T alpha=X[0]; for (auto x:X) chmin(alpha, x); return alpha; } //特別な演算 template pair operator+(const pair &lhs, const pair &rhs){ return pair(lhs.first + rhs.first, lhs.second + rhs.second); } template pair operator-(const pair &lhs, const pair &rhs){ return pair(lhs.first - rhs.first, lhs.second - rhs.second); } template pair operator+=(pair &lhs, const pair &rhs){return lhs=lhs+rhs;} template pair operator-=(pair &lhs, const pair &rhs){return lhs=lhs-rhs;} // 入出力 template void input(T&... a){(cin >> ... >> a);} void print(){cout << "\n";} template void print(const T& a, const Ts&... b){ cout << a; (cout << ... << (cout << " ", b)); cout << "\n"; } template istream &operator>>(istream &is, pair &P){ is >> P.first >> P.second; return is; } template ostream &operator<<(ostream &os, const pair &P){ os << "(" << P.first << ", " << P.second << ")"; return os; } template vector vector_input(int N, int index){ vector X(N+index); for (int i=index; i> X[i]; return X; } template istream &operator>>(istream &is, vector &X){ for (auto &x: X) is >> x; return is; } template ostream &operator<<(ostream &os, const vector &X){ int N=(int)len(X); os << "["; rep(i,N) os << (i ? ", ": "") << X[i]; return os << "]"; } template ostream &operator<<(ostream &os, const unordered_set &S){ os << "{{"; int i=0; for (T a: S) {os << (i ? ", ": "") << a; i++;} return os << "}}"; } template ostream &operator<<(ostream &os, const set &S){ os << "{"; int i=0; for (T a: S) {os << (i ? ", ": "") << a; i++;} return os << "}"; } template ostream &operator<<(ostream &os, const unordered_multiset &S){ os << "{{"; int i=0; for (T a: S) {os << (i ? ", ": "") << a; i++;} return os << "}}"; } template ostream &operator<<(ostream &os, const multiset &S){ os << "{"; int i=0; for (T a: S) {os << (i ? ", ": "") << a; i++;} return os << "}"; } template ostream &operator<<(ostream &os, const unordered_map &M){ os << "{{"; int i=0; for (auto p:M) {os << (i ? ", ": "") << p.first << ": " << p.second; i++;} return os << "}}"; } template ostream &operator<<(ostream &os, const map &M){ os << "{"; int i=0; for (auto p:M) {os << (i ? ", ": "") << p.first << ": " << p.second; i++;} return os << "}"; } bool bit(int S, int k){ return (S>>k)&1; } int main(){ const int N=19; vector> B(N, vector(N, false)); for (int i=0; i> L; for (int j=0; j> a; B[i][a-1]=true; } } int U=(1<>> DP(N+1, vector>(1<{0,0})); DP[0][0][0]=1; for (int t=0; t