Câu chuyện của chúng ta xảy ra vào hai thời điểm khác nhau, vào hai cuộc thi khác nhau.

Nhưng dù thời gian khác nhau, thì không gian cũng đều giống nhau và không có thật: mọi thứ đều được đếm từ \(0\) thay vì đếm từ \(1\).

Câu chuyện 1 - Hội thi Tin học trẻ Toàn quốc

Đề thi của bảng thi C1 là về nhận diện chữ số.

Hesll đã chuyển được các bức ảnh về dưới dạng nhiều dãy có \(n\) bit. Tuy nhiên, nếu chỉ đơn thuần nhét các xâu nhị phân, thì code không thể lưu được nhiều hình ảnh để đối chiếu. Vì vậy, Hesll nhờ vào phép nén Base64.

Một xâu nhị phân \(X\) gồm \(n\) bit \(X_0X_1X_2\dots X_{n-2}X_{n-1}\) có thể được nén về dạng Base64 thành xâu \(X'\) theo các bước như sau:

• Thêm một vài bit \(0\) phía cuối sao cho \(n = |X|\) mới chia hết cho \(6\).
• Nhóm thành \(n'=\dfrac{n}{6}\) nhóm, nhóm thứ \(i\) là xâu nhị phân 6-bit \(X_{6i}X_{6i+1}X_{6i+2}X_{6i+3}X_{6i+4}X_{6i+5}\) (\(0 \le i < n'\)).
• Với mỗi nhóm \(i\), biến từ xâu nhị phân thành một số nguyên bằng phép tính như sau: \(x'_i = \sum\limits_{j=0}^{5} X_{6i+j}\times 2^j\)
• Sau khi thực hiện phép tính ra được số \(x'_i\), ký tự \(X'_i\) sẽ là ký tự ở vị trí \(x'_i\) trong xâu sau (có độ dài \(2^6=64\) ký tự):
  ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/
• Ghép toàn bộ các ký tự \(X'_i\) lại (\(0 \le i < n'\)) để tạo thành xâu \(X'\) có độ dài \(n'\).

Để chuyển ngược lại từ dãy \(X'\) dạng Base64 về thành dãy nhị phân \(X\), ta làm ngược lại quy trình trên.

Phần Input của chúng ta sẽ được nhập vào dưới dạng này. Tuy nhiên, hôm nay trọng tâm của chúng ta không phải là về Base64, vì vậy Hesll sẽ không bắt các bạn phải code nguyên đoạn chuyển đổi từ đầu vào Base64 thành dãy nhị phân. Do đó, các bạn có thể tham khảo code nhập đầu vào ở phần Note.

Câu chuyện 2 - Codeforces

Ở một kỳ thi Codeforces gần đây, bạn Hesll một lần nữa lại đọc nhầm đề mà quên mất rằng, nó chỉ là bài B mà thôi. Hesll đọc nhầm đề bài thành như sau:

Với một xâu nhị phân \(X\) bất kỳ, gọi \(x\) và \(y\) lần lượt là số lượng chữ số \(1\) và \(0\) trong xâu nhị phân đó. Khi đó, trọng số \(w\) của xâu \(X\) là:

Cho xâu \(S\) có \(n = |S|\) là độ dài xâu. Một xâu được gọi là xâu con liên tiếp (gọi tắt là xâu con) của xâu \(S\) nếu nó có thể được tạo bằng cách xóa đi một số ký tự đầu tiên và cuối cùng của xâu. Khi đó, xâu con bắt đầu từ vị trí \(l\), kết thúc tại vị trí \(r\) được gọi là xâu \(S_{l, r}\) \((0 \le l \le r < n)\).

Ví dụ, abc là xâu con liên tiếp của dabce nhưng không phải là xâu con liên tiếp của adbce.

Cho xâu nhị phân \(S\) có độ dài \(n\). Tính \(\sum\limits_{l=0}^{n-1} \sum\limits_{r=l}^{n-1} w(S_{l,r})\), hay nói cách khác là tổng trọng số của mọi xâu con liên tiếp của \(S\).

Tất nhiên, vì đã kể câu chuyện 1, nên xâu đầu vào của chúng ta sẽ có dạng Base64, và chúng ta phải chuyển đổi sang xâu nhị phân có độ dài \(n\) trước khi bắt đầu xử lý thuật toán.

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \leq n \leq 10^7\)) là độ dài xâu \(S\).
• Dòng tiếp theo chứa \(\left\lfloor \dfrac{n-1}{6}+1 \right\rfloor\) ký tự là biểu diễn Base64 của xâu \(S\). Mỗi ký tự chỉ thuộc vào một trong số \(64\) ký tự sau:

            `ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/`
  

Output

• In ra phần dư khi chia đáp án của bài toán cho \(10^9+7\).

Scoring

• Subtask \(1\) (\(15\%\) số điểm): \(n \leq 300\).
• Subtask \(2\) (\(10\%\) số điểm): \(n \leq 5 \times 10^3\).
• Subtask \(3\) (\(10\%\) số điểm): \(n \leq 10^5\), toàn bộ các ký tự của \(S\) đều giống nhau.
• Subtask \(4\) (\(15\%\) số điểm): \(n \leq 10^5\), tồn tại duy nhất một vị trí \(i\) sao cho \(S_i \neq S_{i + 1}\) (\(0 \le i < n-1\)).
• Subtask \(5\) (\(20\%\) số điểm): \(n \le 10^5\).
• Subtask \(6\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

4
G

18

Note

Đoạn code sau giúp chuyển đổi một xâu Base64 kiểu string ra một mảng hằng \(S\).

Đầu tiên, người dùng gọi hàm initBase64() để khởi tạo chức năng xử lý, và sau khi nhập xâu \(S64\) thì gọi hàm b64Conversion(S64) để chuyển đổi và lưu xâu nhị phân thành phẩm gồm các ký tự 0 và 1 vào mảng \(S\).

#include <bits/stdc++.h>
using namespace std;

const char B64[65] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
int position[256];
void initBase64(){
    for (int i = 0; i < 64; i++) {
        position[B64[i]] = i;
    }
}

#define MAX 10000001
int n;
string S64;
char S[MAX];
void b64Conversion(const string &s){
    int ptr = 0;
    for (char c: s){
        int x = position[c];
        for (int i = 0; i < 6; i++){
            S[ptr++] = (x & 1) + '0';
            x >>= 1;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> S64;
    initBase64(); b64Conversion(S64);

    // main logic goes here
}