#include<bits/stdc++.h>
using namespace std;
using LL=long long;
using u64=unsigned long long;
using LF=long double;
#define F(i,l,r) for(int i=l;i<=r;++i)
#define G(i,r,l) for(int i=r;i>=l;--i)
#define CT const&
#define IL inline
#define PB push_back
template<class T>
IL void tomn(T &x,T CT y){y<x?x=y,0:0;}
template<class T>
IL void tomx(T &x,T CT y){y>x?x=y,0:0;}
#define DEBUG(x) cerr<<"line:"<<__LINE__<<" "#x"="<<x<<endl
#define CUT cerr<<"**********\n"
const LF EPS=1e-10L;
IL int dcmp(LF x){return fabs(x)<=EPS?0:(x<0?-1:1);}
const LL INF=4e18L;

const int N=(1<<20)+377;
const LL P=1000000007;
class Arr{
	int d[N],tg,t[N];
public:
	void clr(){++tg;}
	int&operator[](int i){return d[i]&=-(t[i]==tg),t[i]=tg,d[i];}
};
class BIT{
	Arr d;
public:void clr(){d.clr();}
	void upd(int i,int x){for(;i<N;i+=(i&-i))d[i]+=x;}
	int qry(int i){int x=0;for(;i;i-=(i&-i))x+=d[i];return x;}
};
class Heap{
	priority_queue<int> p,q;
	void fix(){while(!p.empty()&&!q.empty()&&(p.top()==q.top()))p.pop(),q.pop();}
public:
	void clr(){
		while(!p.empty())p.pop();
		while(!q.empty())q.pop();
		push(0);
	}
	void push(int x){p.push(x);}
	int top(){return fix(),p.top();}
	void del(int x){q.push(x);}
};
int f[N],g[N],a[N],l[N],r[N],n,si[N];
LL ans[N],pw[N];bool qr[N];
struct Op{int tp,x,y,i;};vector<Op> op[N];
#define L (p<<1)
#define R (L|1)
void dfs1(int p){
	static int tim;
	l[p]=r[p]=++tim,g[tim]=a[p];
	if(L<=n)dfs1(L),dfs1(R),r[p]=tim;
}
void dfs2(int p){
	if(L<=n)dfs2(L),dfs2(R);
	sort(g+l[p],g+r[p]+1),f[l[p]]=g[l[p]];
	if(L<=n)F(i,l[p]+1,r[p])f[i]=*upper_bound(g+l[p],g+r[p]+1,f[i]);
	static Op tmp[N];int tot=0,cnt=0;
	static BIT sum;sum.clr();
	static Heap pq;pq.clr();
	F(i,l[p],r[p])for(Op x:op[i])tmp[++tot]=x;
	sort(tmp+1,tmp+tot+1,[&](Op x,Op y){return x.i<y.i;});
	F(i,1,tot){
		Op x=tmp[i];
		if(x.tp<=2){
			if(x.y==1)x.tp==1?pq.push(x.x):pq.del(x.x);
			else{
				int k=3-(x.tp<<1);
				sum.upd(f[l[x.x]],k),cnt+=k;
			}
		}else if(x.x==p){
			int u=sum.qry(x.y),v=sum.qry(x.y-1),mx=pq.top();
			LL res=(mx<x.y)?(pw[u]-pw[v]+P)%P:(mx==x.y?pw[u]:0);
			ans[x.i]=res*pw[si[x.i]-cnt];
		}
	}
}
int main(){
#ifdef LOCAL
	freopen("C.in","r",stdin);
//	freopen(".out","w",stdout);
#endif
	int h;scanf("%d",&h),n=(1<<h)-1;
	pw[0]=1;F(i,1,N-1)pw[i]=pw[i-1]*2%P;
	F(i,1,n)scanf("%d",a+i);
	dfs1(1);
	int q;scanf("%d",&q);
	F(i,1,q){
		int tp,x,y;scanf("%d%d%d",&tp,&x,&y);
		si[i]=si[i-1]+(y==2?(tp==1?1:(tp==2?-1:0)):0);
		op[l[x]].PB(Op{tp,x,y,i}),qr[i]=(tp==3);
	}dfs2(1);
	F(i,1,q)if(qr[i])printf("%lld\n",ans[i]);
}