#include <stdio.h>
#include <algorithm>
#include <functional>
#include <vector>
#include <queue>
using namespace std;
vector<pair<int, int> > make_tree(int n, vector<int> seq)
{
if (n <= 1) return vector<pair<int, int> >();
vector<int> deg(n + 1);
for (int i = 0; i < n - 2; i++) deg[seq[i]]++;
priority_queue<int, vector<int>, greater<int> > Q;
vector<pair<int, int> > res;
for (int i = 1; i <= n; i++) if (deg[i] == 0) Q.push(i);
for (int i = 0; i < n - 2; i++) {
int x = Q.top(), y = seq[i]; Q.pop();
deg[x]--;
if (--deg[y] == 0) Q.push(y);
res.push_back(make_pair(x, y));
}
int x, y;
for (int i = 1; i <= n; i++) if (deg[i] == 0) { x = i; break; }
for (int i = n; i >= 1; i--) if (deg[i] == 0) { y = i; break; }
res.push_back(make_pair(x, y));
return res;
}
const int n = 4, d = 3;
vector<int> g[n + 1];
long long cnt = 0;
void go2(int x, int l, vector<int> &v)
{
if (l) {
for (int i = 1; i < v.size(); i++) {
{
auto w = v;
reverse(w.begin() + i, w.end());
for (int j = i; j < w.size(); j++) w[j] += v[i - 1];
if (is_sorted(w.begin(), w.end()) || is_sorted(w.rbegin(), w.rend())) cnt++;
}
{
auto w = v;
for (int j = i; j < w.size(); j++) w[j] = -w[j];
for (int j = i; j < w.size(); j++) w[j] += v[i - 1];
if (is_sorted(w.begin(), w.end()) || is_sorted(w.rbegin(), w.rend())) cnt++;
}
}
}
for (auto &y : g[x]) if (y != l) {
v.push_back(y);
go2(y, x, v);
v.pop_back();
}
}
void go(int a, vector<int> &s)
{
if (a == s.size()) {
auto t = make_tree(n, s);
for (int i = 1; i <= n; i++) g[i].clear();
for (auto &p : t) {
g[p.first].push_back(p.second);
g[p.second].push_back(p.first);
}
bool r = 1;
for (int i = 1; i <= n; i++) if (g[i].size() > d) r = 0;
if (r) for (int i = 1; i <= n; i++) {
vector<int> v;
v.push_back(i);
go2(i, 0, v);
}
}
else {
for (int i = 1; i <= n; i++) {
s[a] = i;
go(a + 1, s);
}
}
}
int main()
{
vector<int> s(n - 2);
go(0, s);
printf("%lld\n", cnt);
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDxmdW5jdGlvbmFsPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8cXVldWU+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp2ZWN0b3I8cGFpcjxpbnQsIGludD4gPiBtYWtlX3RyZWUoaW50IG4sIHZlY3RvcjxpbnQ+IHNlcSkKewoJaWYgKG4gPD0gMSkgcmV0dXJuIHZlY3RvcjxwYWlyPGludCwgaW50PiA+KCk7CgoJdmVjdG9yPGludD4gZGVnKG4gKyAxKTsKCWZvciAoaW50IGkgPSAwOyBpIDwgbiAtIDI7IGkrKykgZGVnW3NlcVtpXV0rKzsKCXByaW9yaXR5X3F1ZXVlPGludCwgdmVjdG9yPGludD4sIGdyZWF0ZXI8aW50PiA+IFE7Cgl2ZWN0b3I8cGFpcjxpbnQsIGludD4gPiByZXM7Cglmb3IgKGludCBpID0gMTsgaSA8PSBuOyBpKyspIGlmIChkZWdbaV0gPT0gMCkgUS5wdXNoKGkpOwoJZm9yIChpbnQgaSA9IDA7IGkgPCBuIC0gMjsgaSsrKSB7CgkJaW50IHggPSBRLnRvcCgpLCB5ID0gc2VxW2ldOyBRLnBvcCgpOwoJCWRlZ1t4XS0tOwoJCWlmICgtLWRlZ1t5XSA9PSAwKSBRLnB1c2goeSk7CgkJcmVzLnB1c2hfYmFjayhtYWtlX3BhaXIoeCwgeSkpOwoJfQoKCWludCB4LCB5OwoJZm9yIChpbnQgaSA9IDE7IGkgPD0gbjsgaSsrKSBpZiAoZGVnW2ldID09IDApIHsgeCA9IGk7IGJyZWFrOyB9Cglmb3IgKGludCBpID0gbjsgaSA+PSAxOyBpLS0pIGlmIChkZWdbaV0gPT0gMCkgeyB5ID0gaTsgYnJlYWs7IH0KCXJlcy5wdXNoX2JhY2sobWFrZV9wYWlyKHgsIHkpKTsKCXJldHVybiByZXM7Cn0KCmNvbnN0IGludCBuID0gNCwgZCA9IDM7CnZlY3RvcjxpbnQ+IGdbbiArIDFdOwpsb25nIGxvbmcgY250ID0gMDsKCnZvaWQgZ28yKGludCB4LCBpbnQgbCwgdmVjdG9yPGludD4gJnYpCnsKCWlmIChsKSB7CgkJZm9yIChpbnQgaSA9IDE7IGkgPCB2LnNpemUoKTsgaSsrKSB7CgkJCXsKCQkJCWF1dG8gdyA9IHY7CgkJCQlyZXZlcnNlKHcuYmVnaW4oKSArIGksIHcuZW5kKCkpOwoJCQkJZm9yIChpbnQgaiA9IGk7IGogPCB3LnNpemUoKTsgaisrKSB3W2pdICs9IHZbaSAtIDFdOwoJCQkJaWYgKGlzX3NvcnRlZCh3LmJlZ2luKCksIHcuZW5kKCkpIHx8IGlzX3NvcnRlZCh3LnJiZWdpbigpLCB3LnJlbmQoKSkpIGNudCsrOwoJCQl9CgkJCXsKCQkJCWF1dG8gdyA9IHY7CgkJCQlmb3IgKGludCBqID0gaTsgaiA8IHcuc2l6ZSgpOyBqKyspIHdbal0gPSAtd1tqXTsKCQkJCWZvciAoaW50IGogPSBpOyBqIDwgdy5zaXplKCk7IGorKykgd1tqXSArPSB2W2kgLSAxXTsKCQkJCWlmIChpc19zb3J0ZWQody5iZWdpbigpLCB3LmVuZCgpKSB8fCBpc19zb3J0ZWQody5yYmVnaW4oKSwgdy5yZW5kKCkpKSBjbnQrKzsKCQkJfQoJCX0KCX0KCWZvciAoYXV0byAmeSA6IGdbeF0pIGlmICh5ICE9IGwpIHsKCQl2LnB1c2hfYmFjayh5KTsKCQlnbzIoeSwgeCwgdik7CgkJdi5wb3BfYmFjaygpOwoJfQp9Cgp2b2lkIGdvKGludCBhLCB2ZWN0b3I8aW50PiAmcykKewoJaWYgKGEgPT0gcy5zaXplKCkpIHsKCQlhdXRvIHQgPSBtYWtlX3RyZWUobiwgcyk7CgoJCWZvciAoaW50IGkgPSAxOyBpIDw9IG47IGkrKykgZ1tpXS5jbGVhcigpOwoJCWZvciAoYXV0byAmcCA6IHQpIHsKCQkJZ1twLmZpcnN0XS5wdXNoX2JhY2socC5zZWNvbmQpOwoJCQlnW3Auc2Vjb25kXS5wdXNoX2JhY2socC5maXJzdCk7CgkJfQoJCWJvb2wgciA9IDE7CgkJZm9yIChpbnQgaSA9IDE7IGkgPD0gbjsgaSsrKSBpZiAoZ1tpXS5zaXplKCkgPiBkKSByID0gMDsKCQkKCQlpZiAocikgZm9yIChpbnQgaSA9IDE7IGkgPD0gbjsgaSsrKSB7CgkJCXZlY3RvcjxpbnQ+IHY7CgkJCXYucHVzaF9iYWNrKGkpOwoJCQlnbzIoaSwgMCwgdik7CgkJfQoJfQoJZWxzZSB7CgkJZm9yIChpbnQgaSA9IDE7IGkgPD0gbjsgaSsrKSB7CgkJCXNbYV0gPSBpOwoJCQlnbyhhICsgMSwgcyk7CgkJfQoJfQp9CgppbnQgbWFpbigpCnsKCXZlY3RvcjxpbnQ+IHMobiAtIDIpOwoJZ28oMCwgcyk7CglwcmludGYoIiVsbGRcbiIsIGNudCk7CglyZXR1cm4gMDsKfQ==