Given a Complete Binary Tree of ‘n’ depth, you can perform 4 types of mirror operation on the tree:-

Mirror on the right. The tree is mirrored to the right and rightmost node on every level is connected with the mirrored corresponding node.

Mirror on the left. The tree is mirrored to the left and leftmost node on every level is connected with the mirrored corresponding node.

Mirror on the top. The tree is mirrored to the top and topmost nodes are connected with corresponding nodes.

Mirror on the bottom. The tree is mirrored to the bottom and bottom most nodes are connected with the corresponding nodes.

See the image for details.   
Mirror Right:  

Mirror Bottom:   

You are given ‘q’ queries, each performing this type of operation or asking for the no of edges in the produced graph.

Queries are of the form “1 x” or “2” where x is 1 for right, 2 for left, 3 for top or 4 for bottom.

1 x:  Perform x operation on the result graph.

2:     Print the no of edges in the graph. Since it can be very large, print it modulo 1000000007.   

-----Input:-----
- First line will contain $n$, the depth of the initial tree and $q$, the number of queries.    
- Next $q$ lines contain queries of the form "1 $x$" or "2".

-----Output:-----
For each query of type "2", output a single line containing the no of edges in the graph modulo 1000000007.

-----Constraints-----
- $1 \leq n \leq 1000$
- $1 \leq q \leq 10^5$
- $1 \leq x \leq 4$

-----Sample Input:-----
2 3
1 1
1 4
2

-----Sample Output:-----
38

-----EXPLANATION:-----
Initial no of edges = 6

After the operation 1 1, no of edges = 15

After the operation 1 4, no of edges = 38

At operation 2, we print the no of edges that is 38.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Number theory

Constructive algorithms

Mathematics

Ad-hoc


Solutions:
(n, q) = map(int, input().split())
mod = 1000000007
ans = (pow(2, n + 1, mod) - 2) % mod
top = 1
bottom = pow(2, n, mod)
for i in range(q):
	x = input()
	if x == '2':
		print(ans)
	else:
		x = x.split()
		x = int(x[1])
		if x == 1 or x == 2:
			ans = (2 * ans + n + 1) % mod
			top = 2 * top % mod
			bottom = 2 * bottom % mod
		elif x == 3:
			ans = (2 * ans + top) % mod
			top = bottom
			n = (2 * n + 1) % mod
		else:
			ans = (2 * ans + bottom) % mod
			bottom = top
			n = (2 * n + 1) % mod


import sys
from itertools import *

def numIN(x=' '):
	return map(int, sys.stdin.readline().strip().split(x))
(n, q) = numIN()
ans = 2 ** (n + 1) - 2
l = r = n + 1
b = 2 ** n
u = 1
for _ in range(q):
	x = list(numIN())
	if x[0] == 2:
		print(ans % 1000000007)
	elif x[1] == 1:
		ans *= 2
		ans += r
		b *= 2
		u *= 2
	elif x[1] == 2:
		ans *= 2
		ans += l
		b *= 2
		u *= 2
	elif x[1] == 3:
		ans *= 2
		ans += u
		l *= 2
		r *= 2
		u = b
	else:
		ans *= 2
		ans += b
		l *= 2
		r *= 2
		b = u


(n, q) = list(map(int, input().split()))
(b, e) = (2 ** n, 2 ** (n + 1) - 2)
c = 1
n += 1
for _ in range(q):
	l = input().split()
	if l[0] == '1':
		x = l[1]
		if x == '1' or x == '2':
			e = e * 2 + n
			b *= 2
			c *= 2
		if x == '3':
			e = e * 2 + c
			c = b
			n *= 2
		if x == '4':
			e = e * 2 + b
			b = c
			n *= 2
	else:
		print(e % 1000000007)


mod = 10 ** 9 + 7
(n, q) = map(int, input().split())
top = 1
bottom = 2 ** n % mod
left = (n + 1) % mod
right = (n + 1) % mod
edges = (2 ** n - 1) * 2 % mod
for _ in range(q):
	s = input()
	if int(s[0]) == 1:
		if int(s[2]) == 1:
			edges = (2 * edges % mod + right) % mod
			top = top * 2 % mod
			bottom = bottom * 2 % mod
		elif int(s[2]) == 2:
			edges = (2 * edges % mod + left) % mod
			top = top * 2 % mod
			bottom = bottom * 2 % mod
		elif int(s[2]) == 3:
			edges = (2 * edges % mod + top) % mod
			top = bottom
			left = 2 * left % mod
			right = 2 * right % mod
		else:
			edges = (2 * edges % mod + bottom) % mod
			bottom = top
			left = left * 2 % mod
			right = right * 2 % mod
	else:
		print(edges)


mod = 1000000007
(n, q) = map(int, input().split())
pot = pow(2, n, mod)
e = (pot - 1) * 2 % mod
right = n + 1
left = n + 1
top = 1
bottom = pot
for _ in range(q):
	l = input()
	add = 0
	if l[0] == '1':
		if l[2] == '1':
			add = right
			top *= 2
			bottom *= 2
		elif l[2] == '2':
			add = left
			top *= 2
			bottom *= 2
		elif l[2] == '3':
			add = top
			right *= 2
			left *= 2
			top = bottom
		else:
			add = bottom
			left *= 2
			right *= 2
			bottom = top
		e = (e * 2 + add) % mod
	else:
		print(e)


(n, q) = map(int, input().split())
ans = 2 ** (n + 1)
ans = ans - 2
mod = 1000000007
top = 1
last = 2 ** n
height = n + 1
for i in range(q):
	ty = []
	ty = list(map(int, input().split()))
	if len(ty) == 1:
		print(ans % mod)
	else:
		x = ty[1]
		if x == 1 or x == 2:
			ans = 2 * ans + height
			last = last * 2
			top = top * 2
		elif x == 3:
			ans = 2 * ans + top
			top = last
			height = 2 * height
		else:
			ans = 2 * ans + last
			height = 2 * height
			last = top


(n, k) = map(int, input().split())
b = 2 ** n
t = 1
r = n + 1
number_of_edges = (2 ** (n + 1) - 2) % (10 ** 9 + 7)
for _ in range(k):
	l = list(map(int, input().split()))
	if len(l) > 1:
		if l[1] == 1 or l[1] == 2:
			number_of_edges = (number_of_edges * 2 + r) % (10 ** 9 + 7)
			(t, b) = (t * 2, b * 2)
		elif l[1] == 3:
			number_of_edges = (number_of_edges * 2 + t) % (10 ** 9 + 7)
			r *= 2
			t = b
		elif l[1] == 4:
			number_of_edges = (number_of_edges * 2 + b) % (10 ** 9 + 7)
			r *= 2
			b = t
	if len(l) == 1:
		print(number_of_edges)


import math
s = input()
idx = s.find(' ')
n = int(s[0:idx])
q = int(s[idx + 1:])
r = n + 1
d = math.floor(pow(2, n) + 0.5)
e = 2 * (math.floor(pow(2, n) + 0.5) - 1)
u = 1
MOD = 1000000007
for i in range(0, q):
	k = input()
	k1 = int(k[0])
	if k1 == 1:
		x = int(k[2])
		if x == 1 or x == 2:
			e = 2 * e + r
			u = 2 * u
			d = 2 * d
		elif x == 3:
			e = 2 * e + u
			r = r * 2
			u = d
		else:
			e = 2 * e + d
			r = r * 2
			d = u
	else:
		print(e % MOD)


(n, q) = [int(x) for x in input().split()]
l1 = [1, pow(2, n), n + 1, n + 1]
dict1 = {1: 2, 2: 3, 3: 0, 4: 1}
sum1 = pow(2, n + 1) - 2
flag = 0
for _ in range(q):
	qu = input()
	if int(qu[0]) == 2:
		print(sum1 % 1000000007)
	else:
		num = int(qu[2])
		sum1 = 2 * sum1 + l1[dict1[num]]
		if num > 2:
			flag += 1
			l1[2] = 2 * l1[2]
			l1[3] = 2 * l1[3]
			if num == 3 and flag == 1:
				l1[0] = l1[1]
				flag += 1
			elif num == 4 and flag == 1:
				l1[1] = l1[0]
				flag += 1
		else:
			l1[0] = 2 * l1[0]
			l1[1] = 2 * l1[1]


from sys import *
(n, q) = list(map(int, input().strip().split(' ')))
ans = 1000000007
leaves = 2 ** n
edges = (2 ** (n + 1) - 2) % ans
height = n + 1
op = []
root = 1
for i in range(q):
	s = str(input().strip())
	if s[0] == '2':
		op.append('disp')
	else:
		k = list(map(int, s.split()))
		op.append(k[1])
for j in op:
	if j == 'disp':
		print(edges)
	elif j == 1 or j == 2:
		edges = (2 * edges + height) % ans
		leaves = 2 * leaves % ans
		root = root * 2 % ans
	elif j == 4:
		edges = (2 * edges + leaves) % ans
		leaves = root
		height = 2 * height % ans
	else:
		edges = (2 * edges + root) % ans
		root = leaves
		height = 2 * height % ans


MOD = 1000000007
(levels, q) = input().split()
levels = int(levels)
q = int(q)
left = levels + 1
right = levels + 1
top = 1
bottom = pow(2, levels)
edges = 0
f = 1
for i in range(1, levels + 1):
	f = 2 % MOD * (f % MOD) % MOD
	edges += f
levels += 1
for i in range(1, q + 1):
	l1 = list(map(int, input().split()))
	if l1[0] == 1:
		y = l1[1]
		if y == 1:
			edges = edges % MOD * (2 % MOD) % MOD
			edges = (edges % MOD + levels % MOD) % MOD
			top = top % MOD * (2 % MOD) % MOD
			bottom = bottom % MOD * (2 % MOD) % MOD
		elif y == 2:
			edges = edges % MOD * (2 % MOD) % MOD
			edges = (edges % MOD + levels % MOD) % MOD
			top = top % MOD * (2 % MOD) % MOD
			bottom = bottom % MOD * (2 % MOD) % MOD
		elif y == 3:
			edges = edges % MOD * (2 % MOD) % MOD
			edges = (edges % MOD + top % MOD) % MOD
			top = bottom
			levels = levels % MOD * (2 % MOD)
		elif y == 4:
			edges = edges % MOD * (2 % MOD) % MOD
			edges = (edges % MOD + bottom % MOD) % MOD
			bottom = top
			levels = levels % MOD * (2 % MOD)
	elif l1[0] == 2:
		print(edges % MOD)


n = list(map(int, input().split()))
(a, q) = (n[0], n[1])
n = a
r = int(n + 1)
b = 2 ** n
edge = 2 ** (n + 1) - 2
u = 1
l = n
M = 1000000007
i = 0
while i < q:
	s = list(map(int, input().split()))
	if s[0] == 2:
		print(edge % M)
	elif s[1] == 1 or s[1] == 2:
		edge = edge * 2 % M
		edge = (edge + r) % M
		b = b * 2 % M
		u = u * 2 % M
	elif s[1] == 3:
		edge = edge * 2 % M
		edge = (edge + u) % M
		u = b
		r = r * 2 % M
		l = l * 2 % M
	else:
		edge = edge * 2 % M
		edge = (edge + b) % M
		b = u
		r = r * 2 % M
		l = l * 2 % M
	i += 1


(depth, queries) = map(int, input().strip().split())
mod = 1000 * 1000 * 1000 + 7
left = depth + 1
right = depth + 1
up = 1
down = pow(2, depth)
edges = pow(2, depth + 1) - 2
for i in range(queries):
	typ = input()
	if int(typ[0]) == 1:
		x = int(typ[2])
		if x == 1:
			down = down * 2
			up = up * 2
			edges = edges * 2 + left
		elif x == 2:
			down = down * 2
			up = up * 2
			edges = edges * 2 + right
		elif x == 3:
			edges = edges * 2 + up
			up = down
			left = left * 2
			right = right * 2
		else:
			edges = edges * 2 + down
			down = up
			left = left * 2
			right = right * 2
	else:
		print(edges % mod)


import os, sys
from io import BytesIO, IOBase

def ii():
	return int(input())

def si():
	return input()

def mi():
	return list(map(int, input().split()))

def li():
	return list(mi())
import math
import collections

def CountFrequency(arr):
	return collections.Counter(arr)
for i in range(1):
	(n, q) = mi()
	p = pow(2, n + 1) - 2
	t = 1
	b = pow(2, n)
	s = n + 1
	for i in range(q):
		a = li()
		if len(a) == 2:
			if a[1] == 1 or a[1] == 2:
				p *= 2
				p += s
				t *= 2
				b *= 2
			else:
				p *= 2
				if a[1] == 3:
					p += t
					t = b
					s *= 2
				else:
					p += b
					b = t
					s *= 2
		else:
			print(p % 1000000007)


(n, q) = map(int, input().split())
edges = pow(2, n + 1) - 2
top = 1
bottom = pow(2, n)
side = n + 1
mod = 1000000007
for _ in range(q):
	s = input()
	if s[-1] == '2' and len(s) == 1:
		print(edges % mod)
	elif s[-1] == '1':
		edges = side + edges * 2
		top = 2 * top
		bottom = 2 * bottom
		side = side
	elif s[-1] == '2':
		edges = side + edges * 2
		top = 2 * top
		bottom = 2 * bottom
		side = side
	elif s[-1] == '3':
		edges = top + edges * 2
		top = bottom
		bottom = bottom
		side = side * 2
	elif s[-1] == '4':
		edges = bottom + edges * 2
		top = top
		bottom = top
		side = 2 * side


def lisin():
	a = list(map(int, input().split()))
	return a
if 1:
	(n, q) = lisin()
	eds = n + 1
	edt = 1
	edb = 2 ** n
	edtot = 2 * (edb - 1)
	for qq in range(q):
		x = input().split()
		if len(x) == 2:
			if x[1] == '1' or x[1] == '2':
				edtot *= 2
				edtot += eds
				edt *= 2
				edb *= 2
			elif x[1] == '3':
				edtot *= 2
				edtot += edt
				edt = edb
				eds *= 2
			else:
				edtot *= 2
				edtot += edb
				edb = edt
				eds *= 2
		else:
			print(edtot % 1000000007)


import sys
mod = 10 ** 9 + 7
(n, q) = map(int, input().split())
(u, l, r, d) = (1, n + 1, n + 1, pow(2, n, mod))
e = 2 * (d - 1) % mod
for a in sys.stdin:
	a = list(a.split())
	if a[0] == '1':
		e = e * 2 % mod
		if a[1] == '1':
			e = (e + r) % mod
			r = l
			u = u * 2 % mod
			d = d * 2 % mod
		elif a[1] == '2':
			e = (e + l) % mod
			l = r
			u = u * 2 % mod
			d = d * 2 % mod
		elif a[1] == '3':
			e = (e + u) % mod
			u = d
			l = l * 2 % mod
			r = r * 2 % mod
		else:
			e = (e + d) % mod
			d = u
			l = l * 2 % mod
			r = r * 2 % mod
	else:
		print(e)


(depth, q) = map(int, input().split())
r = 1000000007
edges = 0
top = 1
bottom = 2 ** depth
for i in range(1, depth + 1):
	edges = edges + 2 ** i
for i1 in range(0, q):
	a = list(map(int, input().split()))
	if len(a) == 1:
		print(edges % r)
	else:
		x = a[1]
		if x == 1:
			top = 2 * top
			bottom = 2 * bottom
			edges = 2 * edges + depth + 1
		elif x == 2:
			top = top * 2
			bottom = 2 * bottom
			edges = 2 * edges + depth + 1
		elif x == 3:
			depth = 2 * depth + 1
			edges = 2 * edges + top
			top = bottom
		else:
			depth = 2 * depth + 1
			edges = 2 * edges + bottom
			bottom = top


mod = 1000000007
(n, q) = map(int, input().split())
l = n + 1 % mod
r = n + 1 % mod
t = 1 % mod
b = pow(2, n) % mod
e = (pow(2, n + 1) - 2) % mod
for _ in range(q):
	lst = list(map(int, input().split()))
	if len(lst) != 1:
		if lst[1] == 1:
			e = (2 * e + l) % mod
			l = l
			r = r
			t = 2 * t % mod
			b = 2 * b % mod
		if lst[1] == 2:
			e = (2 * e + r) % mod
			l = l
			r = r
			t = 2 * t % mod
			b = 2 * b % mod
		if lst[1] == 3:
			e = (2 * e + t) % mod
			t = b % mod
			l = 2 * l % mod
			r = 2 * r % mod
			b = b % mod
		if lst[1] == 4:
			e = (2 * e + b) % mod
			b = t % mod
			l = 2 * l % mod
			r = 2 * r % mod
			b = b % mod
	else:
		print(e)


(n, q) = map(int, input().split())
li = list()
ed = 2 ** (n + 1) - 2
rig = n + 1
lef = n + 1
top = 1
bot = 2 ** n
for _ in range(q):
	li = list(map(int, input().split()))
	if li[0] == 1:
		if li[1] == 1:
			ed = 2 * ed + rig
			rig = lef
			top *= 2
			bot *= 2
		elif li[1] == 2:
			ed = 2 * ed + lef
			lef = rig
			top *= 2
			bot *= 2
		elif li[1] == 3:
			ed = 2 * ed + top
			top = bot
			rig *= 2
			lef *= 2
		elif li[1] == 4:
			ed = 2 * ed + bot
			bot = top
			rig *= 2
			lef *= 2
		ed = ed % 1000000007
		top %= 1000000007
		bot %= 1000000007
		rig %= 1000000007
		lef %= 1000000007
	else:
		print(ed % 1000000007)


import math
nq = input()
nq = nq.split()
n = int(nq[0])
q = int(nq[1])
sum = 2 * (pow(2, n) - 1)
bottomedge = pow(2, n)
depthedge = n + 1
topedge = 1
while q > 0:
	q -= 1
	a = input()
	a = a.split()
	if len(a) == 2:
		x = int(a[1])
		if x == 2 or x == 1:
			sum = sum % 1000000007
			sum = sum * 2 + depthedge
			bottomedge *= 2
			topedge *= 2
		elif x == 3:
			sum = sum % 1000000007
			sum = sum * 2 + topedge
			topedge = bottomedge
			depthedge *= 2
		elif x == 4:
			sum = sum % 1000000007
			sum = sum * 2 + bottomedge
			bottomedge = topedge
			depthedge *= 2
	elif len(a) == 1:
		sum = sum % 1000000007
		print(sum)


(n, q) = list(map(int, input().strip().split()))
n += 1
s = n
b = 2 ** (n - 1)
e = 2 * (2 ** (n - 1) - 1) if n > 1 else 0
t = 1
mod = 1000000007
for x in range(q):
	i = input().strip().split()
	if len(i) == 1:
		print(e % mod)
	else:
		e *= 2
		if int(i[1]) <= 2:
			e += s
			b *= 2
			t *= 2
		elif int(i[1]) == 4:
			s *= 2
			e += b
			b = t
		else:
			s *= 2
			e += t
			t = b
		e %= mod


s = input()
l = list(s.split())
n = 0
q = 0
n = int(l[0])
q = int(l[1])
edges = 0
left = 0
right = 0
bottom = 0
top = 0
edges = pow(2, n + 1) - 2
left = n + 1
right = n + 1
top = 1
bottom = pow(2, n)
for i in range(0, q):
	b = input()
	l1 = list(b.split())
	b1 = int(l1[0])
	if b1 == 1:
		a = int(l1[1])
		if a == 1:
			edges = 2 * edges + right
			bottom = 2 * bottom
			top = 2 * top
		elif a == 2:
			edges = 2 * edges + left
			bottom = 2 * bottom
			top = 2 * top
		elif a == 3:
			edges = 2 * edges + top
			top = bottom
			left = 2 * left
			right = 2 * right
		elif a == 4:
			edges = 2 * edges + bottom
			bottom = top
			left = 2 * left
			right = 2 * right
	else:
		print(edges % 1000000007)


(n, m) = map(int, input().split())
edge = pow(2, n + 1, 10 ** 9 + 7)
edge = (edge - 2) % (10 ** 9 + 7)
topnodes = 1
bottomnodes = 2 ** n
n += 1
for i in range(m):
	a = list(map(int, input().split()))
	if a[0] == 1:
		if a[1] == 1:
			edge = (edge * 2 + n) % 1000000007
			bottomnodes *= 2
			topnodes *= 2
		if a[1] == 2:
			edge = (edge * 2 + n) % 1000000007
			bottomnodes *= 2
			topnodes *= 2
		if a[1] == 3:
			edge = (edge * 2 + topnodes) % 1000000007
			topnodes = bottomnodes
			bottomnodes = bottomnodes
			n *= 2
		if a[1] == 4:
			edge = (edge * 2 + bottomnodes) % 1000000007
			bottomnodes = topnodes
			topnodes = topnodes
			n *= 2
	else:
		print(edge)


(n, q) = map(int, input().strip().split())
mod = 1000000007
t = 1
b = pow(2, n)
l = n + 1
r = n + 1
ed = pow(2, n + 1) - 2
for w in range(q):
	s = input()
	if s == '2':
		print(ed % mod)
	else:
		val = s[2]
		val = int(val)
		if val == 1:
			ed += ed + r
			t += t
			b += b
		if val == 2:
			ed += ed + l
			t += t
			b += b
		if val == 3:
			ed += ed + t
			t = b
			l += l
			r += r
		if val == 4:
			ed += ed + b
			b = t
			l += l
			r += r


def main():
	(n, q) = map(int, input().split())
	edges = (pow(2, n, 1000000007) - 1) * 2 % 1000000007
	bottom = pow(2, n, 1000000007)
	top = 1
	right = n + 1
	left = n + 1
	for i in range(q):
		query = list(map(int, input().split()))
		if len(query) == 1:
			print(edges)
		else:
			op = query[1]
			if op == 1:
				edges *= 2
				edges += right
				edges = edges % 1000000007
				bottom *= 2
				top *= 2
			elif op == 2:
				edges *= 2
				edges += left
				edges = edges % 1000000007
				bottom *= 2
				top *= 2
			elif op == 3:
				edges *= 2
				edges += top
				edges = edges % 1000000007
				left *= 2
				right *= 2
				top = bottom
			else:
				edges *= 2
				edges += bottom
				edges = edges % 1000000007
				left *= 2
				right *= 2
				bottom = top
			left = left % 1000000007
			right = right % 1000000007
			bottom = bottom % 1000000007
			top = top % 1000000007
main()


(d, q) = list(map(int, input().split()))
ans = 1000000007
leaves = 2 ** d
edges = (2 ** (d + 1) - 2) % ans
height = d + 1
op = []
root = 1
for i in range(q):
	s = input()
	if s == '2' or s == '2 ' or s == '2  ':
		op.append('show')
	else:
		k = list(map(int, s.split()))
		op.append(k[1])
for j in op:
	if j == 'show':
		print(edges)
	elif j == 1 or j == 2:
		edges = (2 * edges + height) % ans
		leaves = 2 * leaves % ans
		root = root * 2 % ans
	elif j == 4:
		edges = (2 * edges + leaves) % ans
		leaves = root
		height = 2 * height % ans
	else:
		edges = (2 * edges + root) % ans
		root = leaves
		height = 2 * height % ans


(n, q) = map(int, input().split())
ans = pow(2, n + 1) - 2
l = n + 1
d = pow(2, n)
u = 1
for ii in range(q):
	a = list(map(int, input().split()))
	if a[0] == 2:
		print(ans % 1000000007)
	elif a[1] == 1 or a[1] == 2:
		ans *= 2
		ans += l
		d *= 2
		u *= 2
	elif a[1] == 3:
		ans *= 2
		ans += u
		u = d
		l *= 2
	elif a[1] == 4:
		ans *= 2
		ans += d
		d = u
		l *= 2


(n, q) = map(int, input().split())
m = 10 ** 9 + 7
edges = pow(2, n + 1, m)
edges = (edges - 2) % m
depth = n + 1
topnodes = 1
bottomnodes = 2 ** n
for i in range(0, q):
	l1 = list(map(int, input().split()))
	if len(l1) == 1:
		print(edges)
	elif l1[1] == 1 or l1[1] == 2:
		edges = edges * 2 % m
		topnodes *= 2
		edges = (edges + depth) % m
		bottomnodes *= 2
	elif l1[1] == 3:
		edges = edges * 2 % m
		depth *= 2
		edges = (edges + topnodes) % m
		topnodes = bottomnodes
	elif l1[1] == 4:
		edges = edges * 2 % m
		edges = (edges + bottomnodes) % m
		bottomnodes = topnodes
		depth *= 2


m = pow(10, 9) + 7
nq = input().split()
n = int(nq[0])
q = int(nq[1])
e = (pow(2, n + 1) - 2) % m
top = 1
bot = pow(2, n)
r = n + 1
l = n + 1
for qq in range(q):
	qu = input().split()
	if qu[0] == '2':
		print(e)
	else:
		x = int(qu[1])
		if x == 1:
			e = (2 * e + r) % m
			top = top * 2
			bot = bot * 2
		elif x == 2:
			e = (2 * e + l) % m
			top = top * 2
			bot = bot * 2
		elif x == 3:
			e = (2 * e + top) % m
			r = r * 2
			l = l * 2
			top = bot
		else:
			e = (2 * e + bot) % m
			r = r * 2
			l = l * 2
			bot = top


info = [int(j) for j in input().split()]
depth = info[0]
n = info[1]
import math
level = depth + 1
root = 1
leef = int(math.pow(2, depth)) % 1000000007
edge = int(math.pow(2, level)) % 1000000007 - 2
for i in range(n):
	l = [int(j) for j in input().split()]
	if len(l) == 2:
		edge *= 2
		if l[1] <= 2:
			edge = (edge + level) % 1000000007
			root = root * 2 % 1000000007
			leef = leef * 2 % 1000000007
		elif l[1] == 3:
			edge = (edge + root) % 1000000007
			root = leef
			level = level * 2 % 1000000007
		else:
			edge = (edge + leef) % 1000000007
			leef = root
			level = level * 2 % 1000000007
	else:
		print(edge % 1000000007)


import math
import bisect
import itertools
import sys
I = lambda : sys.stdin.readline()
mod = 10 ** 9 + 7

def modu(a, m):
	if a % m:
		return a % m
	return m

def mindiff(a):
	b = a[:]
	b.sort()
	m = 10000000000
	for i in range(len(b) - 1):
		if b[i + 1] - b[i] < m:
			m = b[i + 1] - b[i]
	return m

def lcm(a, b):
	return a * b // math.gcd(a, b)

def merge(a, b):
	i = 0
	j = 0
	c = 0
	ans = []
	while i < len(a) and j < len(b):
		if a[i] < b[j]:
			ans.append(a[i])
			i += 1
		else:
			ans.append(b[j])
			c += len(a) - i
			j += 1
	ans += a[i:]
	ans += b[j:]
	return (ans, c)

def mergesort(a):
	if len(a) == 1:
		return (a, 0)
	mid = len(a) // 2
	(left, left_inversion) = mergesort(a[:mid])
	(right, right_inversion) = mergesort(a[mid:])
	(m, c) = merge(left, right)
	c += left_inversion + right_inversion
	return (m, c)

def is_prime(num):
	if num == 1:
		return False
	if num == 2:
		return True
	if num == 3:
		return True
	if num % 2 == 0:
		return False
	if num % 3 == 0:
		return False
	t = 5
	a = 2
	while t <= int(math.sqrt(num)):
		if num % t == 0:
			return False
		t += a
		a = 6 - a
	return True

def ceil(a, b):
	if a % b == 0:
		return a // b
	else:
		return a // b + 1

def ncr1(n, r):
	s = 1
	for i in range(min(n - r, r)):
		s *= n - i
		s %= mod
		s *= pow(i + 1, mod - 2, mod)
		s %= mod
	return s
(n, q) = map(int, input().split())
e = (pow(2, n + 1, mod) - 2) % mod
a = [0, n + 1, n + 1, 1, pow(2, n, mod)]
for i in range(q):
	b = list(map(int, input().split()))
	if len(b) == 1:
		print(e)
	else:
		(x, y) = (b[0], b[1])
		e = 2 * e + a[y]
		e %= mod
		if y < 3:
			a[3] *= 2
			a[4] *= 2
			a[4] %= mod
			a[3] %= mod
		else:
			a[2] *= 2
			a[1] *= 2
			a[2] %= mod
			a[1] %= mod
			if y == 3:
				a[3] = a[4]
			else:
				a[4] = a[3]


def mirror_down(e, r, l, u, d):
	edge = 2 * e + d
	right = r * 2
	left = l * 2
	up = u
	down = u
	return [edge, right, left, up, down]

def mirror_up(e, r, l, u, d):
	edge = 2 * e + u
	right = r * 2
	left = l * 2
	up = d
	down = d
	return [edge, right, left, up, down]

def mirror_left(e, r, l, u, d):
	edge = 2 * e + l
	right = r
	left = l
	up = u * 2
	down = d * 2
	return [edge, right, left, up, down]

def mirror_right(e, r, l, u, d):
	edge = 2 * e + r
	right = r
	left = l
	up = u * 2
	down = d * 2
	return [edge, right, left, up, down]
s = input('').split(' ')
(n, q) = (int(s[0]), int(s[1]))
e = 2 ** (n + 1) - 2
l = n + 1
r = n + 1
u = 1
d = 2 ** n
while q != 0:
	s = input('').split(' ')
	if len(s) == 2:
		c = int(s[1])
		if c == 1:
			a = mirror_right(e, r, l, u, d)
			e = a[0]
			r = a[1]
			l = a[2]
			u = a[3]
			d = a[4]
		if c == 2:
			a = mirror_left(e, r, l, u, d)
			e = a[0]
			r = a[1]
			l = a[2]
			u = a[3]
			d = a[4]
		if c == 3:
			a = mirror_up(e, r, l, u, d)
			e = a[0]
			r = a[1]
			l = a[2]
			u = a[3]
			d = a[4]
		if c == 4:
			a = mirror_down(e, r, l, u, d)
			e = a[0]
			r = a[1]
			l = a[2]
			u = a[3]
			d = a[4]
	else:
		print(e % 1000000007)
	q -= 1


mod = 10 ** 9 + 7
(n, q) = map(int, input().split())
topbreadth = 1
bottombreadth = pow(2, n, mod)
height = n + 1
edge = 2 * (pow(2, n, mod) - 1) % mod
count1 = 0
count2 = 0
for i in range(q):
	s = input().split()
	if len(s) == 2:
		typ = int(s[1])
		if typ == 1 or typ == 2:
			edge *= 2
			edge += height
			bottombreadth *= 2
			topbreadth *= 2
			topbreadth %= mod
			bottombreadth %= mod
			edge %= mod
		elif typ == 3:
			edge *= 2
			edge += topbreadth
			topbreadth = bottombreadth
			height *= 2
			height %= mod
			edge %= mod
		else:
			edge *= 2
			edge += bottombreadth
			bottombreadth = topbreadth
			height *= 2
			height %= mod
			edge %= mod
	else:
		print(edge)


m = 10 ** 9 + 7
(n, q) = map(int, input().split())
ans = 2 * (2 ** n - 1)
lv = 2 ** n
sd = n + 1
tp = 1
for i in range(q):
	s = input()
	if s[0] == '2':
		print(ans % m)
	else:
		x = int(s[2])
		if x == 1 or x == 2:
			ans = ans * 2 + sd
			lv *= 2
			tp *= 2
		if x == 4:
			ans = ans * 2 + lv
			sd *= 2
			lv = tp
		if x == 3:
			ans = ans * 2 + tp
			sd *= 2
			tp = lv


s = input()
n1 = list(map(int, s.split()))
n = n1[0]
q = n1[1]
nodes = 2 ** (n + 1) - 1
edges = nodes - 1
r = n + 1
l = n + 1
t = 1
b = 2 ** n
m = 0
while m < q:
	s2 = input()
	n2 = list(map(int, s2.split()))
	if len(s2) == 3 and n2[0] == 1:
		a = n2[0]
		x = n2[1]
		if x == 1:
			edges = edges * 2 + r
			t = t * 2
			b = b * 2
		if x == 2:
			edges = edges * 2 + l
			t = t * 2
			b = b * 2
		if x == 3:
			edges = edges * 2 + t
			l = l * 2
			r = r * 2
			t = b
		if x == 4:
			edges = edges * 2 + b
			l = l * 2
			r = r * 2
			b = t
	if len(s2) == 1:
		if n2[0] == 2:
			print(edges % 1000000007)
	m = m + 1


s = input()
l = list(s.split())
n = int(l[0])
q = int(l[1])
e = pow(2, n + 1) - 2
l = n + 1
r = n + 1
t = 1
b = pow(2, n)
for i in range(0, q):
	y = input()
	l6 = list(y.split())
	y1 = int(l6[0])
	if y1 == 1:
		x = int(l6[1])
		if x == 1:
			e = 2 * e + r
			b = 2 * b
			t = 2 * t
		elif x == 2:
			e = 2 * e + l
			b = 2 * b
			t = 2 * t
		elif x == 3:
			e = 2 * e + t
			t = b
			l = 2 * l
			r = 2 * r
		elif x == 4:
			e = 2 * e + b
			b = t
			l = 2 * l
			r = 2 * r
	else:
		print(e % 1000000007)


(n, q) = list(map(int, input().split()))
top = 1
bottom = 2 ** n
depth = n + 1
edges = 2 ** (n + 1) - 2
for _ in range(q):
	x = list(map(int, input().split()))
	if x[0] == 2:
		print(edges % (10 ** 9 + 7))
	else:
		t = x[1]
		edges *= 2
		if t == 1 or t == 2:
			top *= 2
			bottom *= 2
			edges += depth
		if t == 3:
			depth *= 2
			edges += top
			top = bottom
		if t == 4:
			depth *= 2
			edges += bottom
			bottom = top


m = 10 ** 9 + 7
(n, q) = map(int, input().split())
ttttttooooppppp = 1
lllleeeefffttt = n + 1
rrriiiggghhhttt = n + 1
bbboootttooommm = 2 ** n
eeeeddddgggeeeessss = (2 ** (n + 1) - 2) % m
for _ in range(q):
	w = [int(i) for i in input().split()]
	if len(w) == 1:
		print(eeeeddddgggeeeessss)
	else:
		t = w[1]
		if t == 1 or t == 2:
			ttttttooooppppp *= 2
			bbboootttooommm *= 2
			eeeeddddgggeeeessss = (eeeeddddgggeeeessss * 2 + rrriiiggghhhttt) % m
		elif t == 3:
			eeeeddddgggeeeessss = (eeeeddddgggeeeessss * 2 + ttttttooooppppp) % m
			rrriiiggghhhttt *= 2
			lllleeeefffttt = rrriiiggghhhttt
			ttttttooooppppp = bbboootttooommm
		else:
			eeeeddddgggeeeessss = (eeeeddddgggeeeessss * 2 + bbboootttooommm) % m
			rrriiiggghhhttt *= 2
			lllleeeefffttt = rrriiiggghhhttt
			bbboootttooommm = ttttttooooppppp


m = 10 ** 9 + 7
(n, q) = map(int, input().split())
top = 1
left = n + 1
right = n + 1
bottom = 2 ** n
edges = (2 ** (n + 1) - 2) % m
for _ in range(q):
	w = [int(i) for i in input().split()]
	if len(w) == 1:
		print(edges)
	else:
		t = w[1]
		if t == 1 or t == 2:
			top *= 2
			bottom *= 2
			edges = (edges * 2 + right) % m
		elif t == 3:
			edges = (edges * 2 + top) % m
			right *= 2
			left = right
			top = bottom
		else:
			edges = (edges * 2 + bottom) % m
			right *= 2
			left = right
			bottom = top


(n, q) = map(int, input().split())
(top, bottom, e) = (1, 2 ** n, 2 ** (n + 1) - 2)
l = []
for i in range(q):
	l = list(map(int, input().split()))
	if l[0] == 2:
		print(e % (10 ** 9 + 7))
	elif l[1] == 1 or l[1] == 2:
		e = e * 2 + (n + 1)
		top = top * 2
		bottom = bottom * 2
	elif l[1] == 3:
		e = e * 2 + top
		top = bottom
		n = n * 2 + 1
	elif l[1] == 4:
		e = e * 2 + bottom
		bottom = top
		n = n * 2 + 1


d = 1000000007
(n, q) = map(int, input().split())
r = 1
le = 2 ** n
ans = 2 ** (n + 1) - 2
while q > 0:
	q -= 1
	l = list(map(int, input().split()))
	if len(l) == 1:
		print(ans % d)
	elif l[1] == 1 or l[1] == 2:
		ans = (ans * 2 + (n + 1)) % d
		r = r * 2
		le = le * 2
	elif l[1] == 3:
		ans = (ans * 2 + r) % d
		r = le
		n = 2 * n + 1
	else:
		ans = (ans * 2 + le) % d
		le = r
		n = 2 * n + 1


mod = 1000000007
(n, q) = map(int, input().strip().split(' '))
n += 1
down = pow(2, n - 1, mod)
top = 1
depth = n
top = 1
fin = down * 2 - 2
fin %= mod
for i in range(q):
	arr = list(map(int, input().strip().split(' ')))
	if len(arr) == 1:
		print(fin)
	elif arr[1] == 1 or arr[1] == 2:
		fin = fin * 2
		top *= 2
		down *= 2
		fin += depth
	else:
		depth *= 2
		fin *= 2
		if arr[1] == 4:
			fin += down
			down = top
		else:
			fin += top
			top = down
	fin %= mod
	down %= mod
	top %= mod
	depth %= mod


MOD = 1000000007
(n, q) = map(int, input().split())
num_edges = 2 * (2 ** n - 1)
height = n + 1
top = 1
bottom = 2 ** n
for _ in range(q):
	s = input()
	if s[0] == '1':
		op = s[2]
		if op in ['1', '2']:
			num_edges += num_edges + height
			top *= 2
			bottom *= 2
		elif op == '3':
			num_edges += num_edges + top
			top = bottom
			height *= 2
		else:
			num_edges += num_edges + bottom
			bottom = top
			height *= 2
	else:
		print(num_edges % MOD)


(n, q) = map(int, input().split())
edges = 2 * (2 ** n - 1)
side_nodes = n + 1
top_nodes = 1
bottom_nodes = 2 ** n
for i in range(q):
	query = list(map(int, input().split()))
	if query[0] == 1:
		if query[1] == 1 or query[1] == 2:
			edges = edges * 2 + side_nodes
			top_nodes *= 2
			bottom_nodes *= 2
		elif query[1] == 3:
			edges = edges * 2 + top_nodes
			top_nodes = bottom_nodes
			side_nodes *= 2
		else:
			edges = edges * 2 + bottom_nodes
			bottom_nodes = top_nodes
			side_nodes *= 2
	else:
		print(edges % 1000000007)


(n, q) = input().split()
(n, q) = (int(n), int(q))
rt = 1
nd = 2 ** (n + 1) - 1
lf = (nd + 1) // 2
edge = nd - 1
n += 1
for i in range(int(q)):
	ch = list(map(int, input().split(' ')))
	if len(ch) == 2:
		mr = ch[1]
		if mr == 1 or mr == 2:
			edge = edge * 2 + n
			lf = lf * 2
			rt = rt * 2
		elif mr == 3:
			edge = edge * 2 + rt
			n = n * 2
			rt = lf
		else:
			edge = edge * 2 + lf
			n = n * 2
			lf = rt
	else:
		print(edge % (10 ** 9 + 7))


def power(x, y):
	if y == 0:
		return 1
	elif int(y % 2) == 0:
		return power(x, int(y / 2)) * power(x, int(y / 2))
	else:
		return x * power(x, int(y / 2)) * power(x, int(y / 2))
(h, q) = map(int, input().strip().split())
rht = h + 1
lft = h + 1
top = 1
edge = power(2, h + 1) - 2
bottom = power(2, h)
for i in range(1, q + 1):
	type = input()
	if type == '2':
		print(edge % 1000000007)
	else:
		y = type[2]
		y = int(y)
		if y == 1:
			edge = edge * 2 + rht
			top = top * 2
			bottom = bottom * 2
		elif y == 2:
			edge = edge * 2 + lft
			top = top * 2
			bottom = bottom * 2
		elif y == 3:
			edge = edge * 2 + top
			top = bottom
			lft = lft * 2
			rht = rht * 2
		elif y == 4:
			edge = edge * 2 + bottom
			bottom = top
			lft = lft * 2
			rht = rht * 2


def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
(n, q) = map(int, input().split())
e = (power(2, n, 10 ** 9 + 7) - 1) * 2
t = 1
b = power(2, n, 10 ** 9 + 7)
r = n + 1
for i in range(q):
	l = list(map(int, input().split()))
	if l[0] == 1:
		if l[1] == 1 or l[1] == 2:
			e = (2 * e + r) % (10 ** 9 + 7)
			b = 2 * b % (10 ** 9 + 7)
			t = 2 * t % (10 ** 9 + 7)
		elif l[1] == 3:
			e = (2 * e + t) % (10 ** 9 + 7)
			r = 2 * r % (10 ** 9 + 7)
			t = b % (10 ** 9 + 7)
		else:
			e = (2 * e + b) % (10 ** 9 + 7)
			r = 2 * r % (10 ** 9 + 7)
			b = t % (10 ** 9 + 7)
	elif l[0] == 2:
		print(e)


arr = list(map(int, input().split()))
h = arr[0]
e = 2 ** (h + 1)
e1 = e - 2
l = h + 1
r = h + 1
u = 1
d = 2 ** h
while arr[1]:
	arr[1] = arr[1] - 1
	arr1 = list(map(int, input().split()))
	if arr1[0] == 2:
		print(e1 % 1000000007)
	elif arr1[1] == 1:
		e1 = e1 * 2
		e1 = e1 + r
		u = u * 2
		d = d * 2
		e1 = e1 % 1000000007
	elif arr1[1] == 2:
		e1 = e1 * 2
		e1 = e1 + l
		u = u * 2
		d = d * 2
		e1 = e1 % 1000000007
	elif arr1[1] == 3:
		e1 *= 2
		e1 = e1 + u
		u = d
		l = l * 2
		r = r * 2
		e1 = e1 % 1000000007
	elif arr1[1] == 4:
		e1 *= 2
		e1 = e1 + d
		d = u
		l = l * 2
		r = r * 2
		e1 = e1 % 1000000007


(n, q) = map(int, input().split())
e = 2 ** (n + 1) - 2
l = 2 ** n
h = n + 1
p = 1
up = 0
down = 1
for i in range(q):
	qi = input().split()
	if qi[0] == '2':
		print(e % 1000000007)
	elif qi[1] == '1' or qi[1] == '2':
		e = e * 2 + h
		l = l * 2
		p = p * 2
	elif qi[1] == '3':
		if up == 1:
			e = e * 2 + l
		else:
			e = e * 2 + p
		up = down
		h = h * 2
	else:
		if down == 1:
			e = e * 2 + l
		else:
			e = e * 2 + p
		down = up
		h = h * 2


(n, q) = map(int, input().rstrip().split())
u = 1
d = 2 ** n
l = 2 * (2 ** n - 1)
tr = False
lt = n + 1
for i in range(q):
	l = l % 1000000007
	te = input().rstrip().split()
	if int(te[0]) == 2:
		print(l)
	else:
		op = int(te[1])
		if op == 1 or op == 2:
			u = 2 * u
			d = 2 * d
			l = 2 * l + lt
		elif tr:
			l = 2 * l + u
			lt = 2 * lt
		else:
			if op == 3:
				l = 2 * l + u
				lt = lt * 2
				u = d
			else:
				l = 2 * l + d
				lt = lt * 2
				d = u
			tr = True


try:
	(n, q) = list(map(int, input().split()))
	(L, R, T, B) = (n + 1, n + 1, 1, 2 ** n)
	total = 0
	for val in range(1, n + 1):
		total += 2 ** val
	for _ in range(q):
		i = list(map(int, input().split()))
		if i[0] == 1:
			if i[1] == 1:
				total *= 2
				total += R
				(L, R, T, B) = (L, R, 2 * T, B * 2)
			if i[1] == 2:
				total *= 2
				total += L
				(L, R, T, B) = (L, R, 2 * T, B * 2)
			if i[1] == 3:
				total *= 2
				total += T
				(L, R, T, B) = (2 * L, 2 * R, B, B)
			if i[1] == 4:
				total *= 2
				total += B
				(L, R, T, B) = (2 * L, 2 * R, T, T)
		else:
			print(total % 1000000007)
except:
	pass


def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
[n, q] = [int(i) for i in input().split()]
su = (power(2, n + 1, 1000000007) - 2 + 1000000007) % 1000000007
width = 1
t = 0
k = n + 1
while q > 0:
	a = [int(i) for i in input().split()]
	if a[0] == 2:
		print(su)
	elif a[1] == 1 or a[1] == 2:
		su = (2 * su % 1000000007 + k % 1000000007) % 1000000007
		width = width * 2 % 1000000007
	elif a[1] == 3:
		if t == 0:
			su = (2 * su % 1000000007 + width % 1000000007) % 1000000007
			t = 1
		elif t == 1:
			su = (2 * su % 1000000007 + width % 1000000007 * power(2, n, 1000000007) % 1000000007) % 1000000007
		elif t == 2:
			su = (2 * su % 1000000007 + width % 1000000007) % 1000000007
		k = k * 2 % 1000000007
	elif a[1] == 4:
		if t == 2:
			su = (2 * su % 1000000007 + width % 1000000007) % 1000000007
		elif t == 0:
			su = (2 * su % 1000000007 + width % 1000000007 * power(2, n, 1000000007) % 1000000007) % 1000000007
			t = 2
		elif t == 1:
			su = (2 * su % 1000000007 + width % 1000000007 * power(2, n, 1000000007) % 1000000007) % 1000000007
		k = k * 2 % 1000000007
	q -= 1


(n, q) = input().split()
n = int(n)
q = int(q)
r = n + 1
l = n + 1
b = 2 ** n
t = 1
edge = 0
MOD = 1000000007
for i in range(1, n + 1):
	edge += 2 ** i
for i in range(q):
	l1 = list(map(int, input().split()))
	if l1[0] == 1:
		if l1[1] == 1:
			edge = (edge % MOD * 2 + r) % MOD
			r = r % MOD
			l = l % MOD
			b = 2 * (b % MOD)
			t = 2 * (t % MOD)
		elif l1[1] == 2:
			edge = (edge % MOD * 2 + l) % MOD
			r = r % MOD
			l = l % MOD
			b = 2 * (b % MOD)
			t = 2 * (t % MOD)
		elif l1[1] == 3:
			edge = (edge % MOD * 2 + t) % MOD
			t = b % MOD
			b = b % MOD
			r = 2 * (r % MOD)
			l = 2 * (l % MOD)
		elif l1[1] == 4:
			edge = (edge % MOD * 2 + b) % MOD
			b = t % MOD
			t = t % MOD
			r = 2 * (r % MOD)
			l = 2 * (l % MOD)
	else:
		print(edge % MOD)


import math
(n, q) = map(int, input().split())
edg = 2 ** (n + 1) - 2
h = n + 1
top = 1
bot = 2 ** n
for i in range(q):
	a = list(map(int, input().split()))
	if len(a) == 2:
		if a[1] == 1 or a[1] == 2:
			edg = 2 * edg + h
			bot = 2 * bot
			top = 2 * top
		elif a[1] == 3:
			edg = 2 * edg + top
			h = 2 * h
			top = bot
		elif a[1] == 4:
			edg = 2 * edg + bot
			bot = top
			h = 2 * h
	else:
		print(edg % 1000000007)


(n, q) = [int(a) for a in input().split()]
e = pow(2, n + 1) - 2
l = [1, pow(2, n), n + 1, n + 1]
d = {1: 2, 2: 3, 3: 0, 4: 1}
f = 0
for _ in range(q):
	x = input()
	if int(x[0]) == 2:
		print(e % 1000000007)
	else:
		x1 = int(x[2])
		e = 2 * e + l[d[x1]]
		if x1 > 2:
			f = f + 1
			l[2] = 2 * l[2]
			l[3] = 2 * l[3]
			if x1 == 3 and f == 1:
				l[0] = l[1]
				f = f + 1
			elif x1 == 4 and f == 1:
				l[1] = l[0]
				f = f + 1
		else:
			l[0] = 2 * l[0]
			l[1] = 2 * l[1]


(n, q) = map(int, input().split())
topNodes = 1
bottomNodes = 2 ** n
leftNodes = n + 1
rightNodes = n + 1
edges = 2 ** (n + 1) - 2
for i in range(q):
	inp = input()
	if len(inp) > 1:
		(cmd, dir) = map(int, inp.split())
		if dir == 1:
			edges = 2 * edges + rightNodes
			bottomNodes = 2 * bottomNodes
			topNodes = 2 * topNodes
		elif dir == 2:
			edges = 2 * edges + leftNodes
			bottomNodes = 2 * bottomNodes
			topNodes = 2 * topNodes
		elif dir == 3:
			edges = 2 * edges + topNodes
			leftNodes = 2 * leftNodes
			rightNodes = 2 * rightNodes
			topNodes = bottomNodes
		elif dir == 4:
			edges = 2 * edges + bottomNodes
			leftNodes = 2 * leftNodes
			rightNodes = 2 * rightNodes
			bottomNodes = topNodes
	else:
		print(edges % 1000000007)


(n, q) = map(int, input().split())
c = 2 * (pow(2, n) - 1)
ns = n + 1
nt = 1
nb = pow(2, n)
x = 7 + pow(10, 9)
for i in range(q):
	li = list(map(int, input().split()))
	if len(li) == 1:
		print(c % x)
	else:
		b = li[1]
		if b == 1 or b == 2:
			c = 2 * c + ns
			nt *= 2
			nb *= 2
		elif b == 3:
			c = 2 * c + nt
			ns *= 2
			nt = nb
		else:
			c = 2 * c + nb
			ns *= 2
			nb = nt