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.

Difficulty: interview

Starter code:

Solutions:
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)


# cook your dish here
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)

# cook your dish here
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)


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, 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


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)


def mirror_down(e,r,l,u,d):
 edge=(2*e)+d
 right=r*2
 left=l*2
 up=u
 down=u
 #print(edge,right,left,up,down)
 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
 #print(edge,right,left,up,down)
 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
 #print(edge,right,left,up,down)
 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
 #print(edge,right,left,up,down)
 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=1000000007
n,q=map(int,input().split())
pot=pow(2,n,mod) #2 to the power n and then mod 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)

def main():
 n,q = list(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()


import sys
mod=10**9+7
n,q=list(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)
  


# cook your dish here
depth,q=list(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
    
   
  


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=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)