#include <bits/stdc++.h>
using namespace std;
namespace {
const int N = 142;
vector<int64_t> dp;
pair<vector<int>, int> unrank(int64_t x) { // find the x-th sequence (0 indexed)
// if #(len1) = 5 and x=5 then we subtract
int len = 1;
while (x >= dp[len]) {
x -= dp[len++];
}
// find the ith sequence with this length
// order: nothing, 2, 3
int ans_len = len;
vector<int> ans;
while (len) {
// 5 sequences in cat A, 10 in cat B, 3 in cat C
int num_emp = 1, num_2, num_3;
if (len <= 3) {
num_2 = len >= 2, num_3 = len >= 3;
} else {
num_2 = dp[len - 2], num_3 = dp[len - 3];
}
if (x >= num_emp + num_2) {
ans.push_back(3);
x -= num_emp + num_2, len -= 3;
} else if (x >= num_emp) {
ans.push_back(2);
x -= num_emp, len -= 2;
} else {
break;
}
}
reverse(ans.begin(), ans.end());
return {ans, ans_len};
}
} // namespace
int Declare() {
// 2s are 1s, 3s are 0s
// sum 1 => {}
// sum 2 => {}, {2}
// sum 3 => {}, {2}, {3} (note that they aren't repeated and are distinguished by length)
dp.resize(N + 1);
dp[0] = 1, dp[1] = 1, dp[2] = 2;
for (int i = 3; i <= N; ++i) {
dp[i] = dp[i - 2] + dp[i - 3] + 1; // +1 means empty sequence
}
return N;
}
pair<vector<int>, vector<int>> Anna(long long A) {
auto [seq, len] = unrank(A);
vector<int> a;
for (int &i : seq) {
if (i == 3) {
a.push_back(0), a.push_back(0), a.push_back(0);
} else {
a.push_back(1), a.push_back(1);
}
}
while (a.size() != len) {
a.push_back(a.size() & 1);
}
vector<int> b(a.size());
for (int i = 0; i < a.size(); i++) {
b[i] = (i + 1) & 1;
}
return {a, b};
}
#include <bits/stdc++.h>
using namespace std;
namespace {
const int N = 142;
vector<int64_t> dp;
int64_t rerank(vector<int> seq, int len) {
int64_t ans = 0;
for (int i = 1; i < len; ++i) {
ans += dp[i];
}
while (!seq.empty()) {
// dp[len] = 1 + dp[len-2] + dp[len-3]
// that is, either empty, or 2, or 3
int num_emp = 1, num_2, num_3;
if (len <= 3) {
num_2 = len >= 2, num_3 = len >= 3;
} else {
num_2 = dp[len - 2], num_3 = dp[len - 3];
}
if (seq.back() == 2) {
ans += num_emp, len -= 2;
} else { // == 3
ans += num_emp + num_2, len -= 3;
}
seq.pop_back();
}
return ans;
}
} // namespace
long long Bruno(vector<int> u) {
dp.resize(N + 1);
dp[0] = 1, dp[1] = 1, dp[2] = 2;
for (int i = 3; i <= N; ++i) {
dp[i] = dp[i - 2] + dp[i - 3] + 1;
}
// here we do dp again: partition u => {a, b} such that
// - a is 11/000 then 0101...
// - b is 1010...
// dp[ia][ib][noise_a][n0][n1][cur_b]
// for each i we decide whether it goes to a or b
const int n = u.size() / 2;
vector vld(n + 1, vector(n + 1, vector(2, vector(4, vector(3, vector<int>(2)))))); // valid = vld
auto process = [&](int ia, int ib, int noise_a, int n0, int n1, int cur_b) {
if (n0 != 0 && n1 != 0) { // both can't be non-zero
vld[ia][ib][noise_a][n0][n1][cur_b] = false;
return;
}
if (noise_a && (n0 != 0 || n1 != 0)) { // can't push if we're in noise mode
vld[ia][ib][noise_a][n0][n1][cur_b] = false;
return;
}
if (ia == n && ib == n) { // filled both sequences
vld[ia][ib][noise_a][n0][n1][cur_b] = n0 == 0 && n1 == 0;
return;
}
// push n0 or n1
if (n0 == 3 && ia + 3 <= n) {
vld[ia][ib][noise_a][n0][n1][cur_b] |= vld[ia + 3][ib][noise_a][0][n1][cur_b];
}
if (n1 == 2 && ia + 2 <= n) {
vld[ia][ib][noise_a][n0][n1][cur_b] |= vld[ia + 2][ib][noise_a][n0][0][cur_b];
}
// switch to noise mode
if (!noise_a) {
vld[ia][ib][0][n0][n1][cur_b] |= vld[ia][ib][1][n0][n1][cur_b];
}
int i = ia + ib + n0 + n1;
if (i >= 2 * n) {
return;
}
// noise mode a push
if (ia + 1 <= n && noise_a && u[i] == (ia & 1)) {
vld[ia][ib][1][n0][n1][cur_b] |= vld[ia + 1][ib][1][n0][n1][cur_b];
}
// try pushing to a
if (u[i] == 0 && n0 + 1 <= 3) {
vld[ia][ib][noise_a][n0][n1][cur_b] |= vld[ia][ib][noise_a][n0 + 1][n1][cur_b];
} else if (u[i] == 1 && n1 + 1 <= 2) {
vld[ia][ib][noise_a][n0][n1][cur_b] |= vld[ia][ib][noise_a][n0][n1 + 1][cur_b];
}
// otherwise try pushing to b
if (ib + 1 <= n && u[i] == cur_b) {
vld[ia][ib][noise_a][n0][n1][cur_b] |= vld[ia][ib + 1][noise_a][n0][n1][1 - cur_b];
}
};
for (int ia = n; ia >= 0; --ia) {
for (int ib = n; ib >= 0; --ib) {
for (int noise_a = 1; noise_a >= 0; --noise_a) {
for (int n0 = 3; n0 >= 0; --n0) {
for (int n1 = 2; n1 >= 0; --n1) {
for (int cur_b = 1; cur_b >= 0; --cur_b) {
process(ia, ib, noise_a, n0, n1, cur_b);
}
}
}
}
}
}
vector<int> seq;
int ia = 0, ib = 0, noise_a = 0, n0 = 0, n1 = 0, cur_b = 1;
assert(vld[ia][ib][noise_a][n0][n1][cur_b]);
while (ia != n || ib != n) {
// push n0 or n1
if (n0 == 3 && ia + 3 <= n && vld[ia + 3][ib][noise_a][0][n1][cur_b]) {
seq.push_back(3);
ia += 3, n0 = 0;
continue;
}
if (n1 == 2 && ia + 2 <= n && vld[ia + 2][ib][noise_a][n0][0][cur_b]) {
seq.push_back(2);
ia += 2, n1 = 0;
continue;
}
// switch to noise mode
if (!noise_a && vld[ia][ib][1][n0][n1][cur_b]) {
noise_a = 1;
continue;
}
int i = ia + ib + n0 + n1;
assert(i != 2 * n);
// noise mode a push
if (ia + 1 <= n && noise_a && u[i] == (ia & 1) && vld[ia + 1][ib][1][n0][n1][cur_b]) {
ia += 1;
continue;
}
// try pushing to a
if (u[i] == 0 && n0 + 1 <= 3 && vld[ia][ib][noise_a][n0 + 1][n1][cur_b]) {
n0 += 1;
continue;
} else if (u[i] == 1 && n1 + 1 <= 2 && vld[ia][ib][noise_a][n0][n1 + 1][cur_b]) {
n1 += 1;
continue;
}
// otherwise try pushing to b
if (ib + 1 <= n && u[i] == cur_b && vld[ia][ib + 1][noise_a][n0][n1][1 - cur_b]) {
ib += 1, cur_b = 1 - cur_b;
continue;
}
}
return rerank(seq, n);
}
