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é