Vào một buổi chiều đẹp trời, Thu đang thong thả học kiến thức lập trình thi đấu thì người bạn thân của cô là Bi nhắn tin đến, hỏi Thu một bài toán, muốn biết Thu có làm được không. Bài toán được mô tả như sau:

Cho một xâu độ dài $n$ chỉ gồm các ký tự 0 và 1, định nghĩa giá trị đóng góp của xâu là tổng các bình phương của độ dài các đoạn ký tự 1 liên tiếp trong xâu. Ví dụ: xâu 1011001 có giá trị đóng góp là $1^2+2^2+1^2=6$ .

Bây giờ Bi đổi một số ký tự trong xâu (có thể không có hoặc có nhiều ký tự) thành ?, tức là mỗi ký tự bị đổi thành ? có xác suất là 0 hay là 1 đều bằng $\dfrac{1}{2}$ . Hỏi kỳ vọng của giá trị đóng góp của xâu sau khi thay đổi là bao nhiêu (đáp án lấy modulo $10^9+7$ )?

Ví dụ: với xâu 11?00, khi ký tự ? là 0 thì xâu trở thành 11000, có giá trị đóng góp là $2^2=4$ ; khi ký tự ? là 1 thì xâu trở thành 11100, có giá trị đóng góp là $3^2=9$ ; vậy kỳ vọng giá trị đóng góp của xâu này là $\dfrac{4+9}{2}=\dfrac{13}{2}$ .

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $n$ , biểu thị độ dài của xâu.

Dòng thứ hai chứa một xâu $S$ , là xâu đã bị thay đổi trong bài toán trên, chỉ gồm ba loại ký tự 0, 1, ?.

Dữ liệu ra

In ra một số nguyên, là kỳ vọng sau khi lấy modulo $10^9+7$ .

Đặt $M=10^9+7$ , có thể chứng minh giá trị cần tìm viết được dưới dạng phân số tối giản $\dfrac{p}{q}$ , trong đó $p,q$ là các số nguyên và $q\not\equiv0\pmod M$ . Số nguyên cần in ra là $p\cdot q^{-1}\pmod M$ .

Ví dụ

Input

5
11?00

Output

500000010

Ghi chú

Giới hạn dữ liệu

Với tất cả các test, $1\le n\le 2\times 10^5$ .