Gọi ~D~ là số lượng số ~0~, ~D=S-A-B-C~

Biểu diễn tứ phân của số cần tìm bằng mảng ~a[]~, ví dụ ~25~ thì ~a[]=[1,2,1]~

Với mỗi ~1 \leq i \leq S~ ~div~ ~2~ + ~S~ ~mod~ ~2~, ta có ~j = S - i + 1~, khi đó ~a[i]=a[j]~ (đối xứng). Vì vậy ta cần số lượng số của mỗi chữ số luôn chẵn ~(A~ ~mod~ ~2 + B~ ~mod~ ~2 + C~ ~mod~ ~2 + D~ ~mod~ ~2=0)~, hoặc ~A~, ~B~, ~C~, ~D~ chỉ có một số lẻ khi ~S~ lẻ ~(A~ ~mod~ ~2 + B~ ~mod~ ~2 + C~ ~mod~ ~2 + D~ ~mod~ ~2=1)~ vì trong trường hợp ~S~ lẻ thì sẽ xuất hiện vị trí ~i = j =~ ~S~ ~div~ ~2~ ~+ S~ ~mod~ ~2~

Ta tiến hành xây dựng mảng ~a[]~. Khi đặt tại vị trí ~i~ thì đồng thời đặt luôn vị trí ~j~ tương ứng ~(a[i] = a[j])~ theo thứ tự số bé đặt trước, số lớn đặt sau. Chú ý: tại vị trí ~i=1,j=S~ thì không được đặt số ~0~ vô nghĩa (nếu ~S=1~ thì vẫn có thể đặt ~0~ được).

Sau khi có mảng biểu diễn tứ phân của kết quả, ta chuyển sang hệ thập phân ~ans=\sum_{i=1}^n (a_i*4^{p-1})~

Các bạn nhớ mod ~727355608~ nhé

Code mẫu

/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")*/
// only when really needed

/* GNU G++17 7.3.0: No long long for faster code
   GNU G++17 9.2.0 (64 bit, msys 2): Long long only for faster code */

#include <bits/stdc++.h>

#define for1(i,a,b) for (int i = a; i <= b; i++)
#define for2(i,a,b) for (int i = a; i >= b; i--)
#define int long long

#define sz(a) (int)a.size()
#define pii pair<int,int>

/*
__builtin_popcountll(x) : Number of 1-bit
__builtin_ctzll(x) : Number of trailing 0
*/

#define PI 3.1415926535897932384626433832795
#define INF 1000000000000000000
#define MOD 727355608
#define MOD2 1000000009
#define EPS 1e-6

using namespace std;

int cnt[4];
int mid, res;
string s, t;

signed main() {

    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    // freopen("cf.inp", "r", stdin);
    // freopen("cf.out", "w", stdout);

    for1(i,0,3) cin >> cnt[i];
    mid = -1;
    cnt[0] -= cnt[1] + cnt[2] + cnt[3];
    for1(i,0,3) if (cnt[i] & 1) {
        if (mid == -1) {
            mid = i;
            cnt[i]--;
        }
        else {
            cout << "Bedao!";
            return 0;
        }
    }

    for1(i,0,3) cnt[i] /= 2;
    for1(i,0,3) {
        for1(j,1,cnt[i]) s += char(i);
    }
    for1(i,0,sz(s) - 1) if (s[i] > 0) {
        swap(s[i], s[0]);
        break;
    }

    t = s;
    reverse(t.begin(), t.end());
    if (mid != -1) s += char(mid);
    s += t;

    if(sz(s) > 1 && s[0] == 0){
        cout << "Bedao!";
        return 0;
    }

    for (auto i : s) res = (res * 4 + i) % MOD;
    cout << res;

}