Tô màu khối Rubik (bản khó)

Cho một cây nhị phân hoàn chỉnh gồm $2^k-1$ đỉnh: mỗi đỉnh $i$ với $1\le i\le 2^{k-1}-1$ có đúng hai con là đỉnh $2i$ và $2i+1$; các đỉnh từ $2^{k-1}$ đến $2^k-1$ là lá (không có con).

Bạn cần tô màu mọi đỉnh của cây bằng $6$ màu của khối Rubik: Trắng, Vàng, Xanh lá, Xanh dương, Đỏ, Cam.

Một cách tô màu được gọi là hợp lệ nếu mọi cạnh nối hai đỉnh có màu là hai mặt kề nhau trên khối Rubik. Cụ thể, các cặp màu đối nhau (không kề nhau) là: Trắng và Vàng, Xanh lá và Xanh dương, Đỏ và Cam. Hai đỉnh nối bởi một cạnh không được tô cùng màu, cũng không được tô hai màu đối nhau. Nói cách khác, với mỗi màu có đúng $4$ màu kề với nó.

Tuy nhiên, có $n$ đỉnh đặc biệt đã được tô màu sẵn; các đỉnh này bắt buộc phải giữ nguyên màu đã cho.

Hãy đếm số cách tô màu hợp lệ toàn bộ cây. Hai cách tô là khác nhau nếu có ít nhất một đỉnh được tô màu khác nhau. Vì kết quả có thể rất lớn, hãy in ra kết quả theo modulo ${10}^9+7$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $k$: số tầng của cây nhị phân hoàn chỉnh.
• Dòng thứ hai chứa số nguyên $n$: số đỉnh đã được tô màu sẵn.
• $n$ dòng tiếp theo, mỗi dòng chứa một số nguyên $v$ và một xâu $s$: chỉ số đỉnh và màu của đỉnh đó. Xâu $s$ là một trong sáu xâu white, yellow, green, blue, red, orange (lần lượt tương ứng với Trắng, Vàng, Xanh lá, Xanh dương, Đỏ, Cam).

Mỗi đỉnh $v$ xuất hiện nhiều nhất một lần trong dữ liệu vào.

Dữ liệu ra

In ra một số nguyên: số cách tô màu hợp lệ theo modulo ${10}^9+7$.

Ràng buộc

• $1\le k\le 60$
• $1\le n\le min(2^k-1,2000)$
• $1\le v\le 2^k-1$

Ví dụ