1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
//mt19937 mrand(random_device{}());
const ll mod=1000000007;
//int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
int gcd(int a,int b) { return b?gcd(b,a%b):a;}
// head

const int N=5e5+5;

#define INF 0x3f3f3f3f

template<class T> inline void read(T &x) {
    x=0; int c=getchar(),f=1;
    for (;!isdigit(c);c=getchar()) if (c==45) f=-1;
    for (;isdigit(c);c=getchar()) (x*=10)+=f*(c-'0');
}
int n,a[N],b[N],rootA,rootB,leftSonA[N],leftSonB[N],rightSonA[N],rightSonB[N],
sz[N],act[N],dp[N],ans;

//n^2 niestety:(((

void dfsA(int u,bool dir,bool ok) {
	sz[u]=1;
	if (!ok) act[u]=u;
	if (leftSonA[u]!=-1) {
		act[leftSonA[u]]=act[u];
		dfsA(leftSonA[u],0,(ok||dir));
		if (dir) dp[u]=sz[leftSonA[u]];
	}
	if (rightSonA[u]!=-1) {
		act[rightSonA[u]]=act[u];
		dfsA(rightSonA[u],1,(ok||!dir));
		if (!dir) dp[u]=sz[rightSonA[u]];
	}
	sz[u]+=sz[leftSonA[u]]+sz[rightSonA[u]];
}

void dfsB(int verOfA,int verOfB) {
	memset(dp,0,sizeof(dp));
	if (verOfB<verOfA) {
		dfsA(leftSonA[verOfA],0,0);
		if (verOfB!=act[verOfB]) rightSonA[act[verOfB]]=-1;
		rep(i,act[verOfB]+1,verOfB) leftSonA[i]=i-1,rightSonA[i]=-1,ans=(ans+dp[i])%mod;
		rightSonA[verOfB]=verOfB+1;
		if (verOfB!=act[verOfB]) {
			leftSonA[verOfB]=verOfB-1;
			ans=(ans+dp[verOfB])%mod;
		}
		per(i,verOfB+1,verOfA) leftSonA[i]=-1,rightSonA[i]=i+1,ans=(ans+dp[i])%mod;
		leftSonA[verOfA]=-1;
		ans=(ans+dp[act[verOfB]]+verOfA-verOfB)%mod;
	}
	else if (verOfB>verOfA) {
		dfsA(rightSonA[verOfA],1,0);
		if (verOfB!=act[verOfB]) leftSonA[act[verOfB]]=-1;
		per(i,verOfB+1,act[verOfB]) leftSonA[i]=-1,rightSonA[i]=i+1,ans=(ans+dp[i])%mod;
		leftSonA[verOfB]=verOfB-1;
		if (verOfB!=act[verOfB]) {
			rightSonA[verOfB]=verOfB+1;
			ans=(ans+dp[verOfB])%mod;
		}
		rep(i,verOfA+1,verOfB) leftSonA[i]=i-1,rightSonA[i]=-1,ans=(ans+dp[i])%mod;
		rightSonA[verOfA]=-1;
		ans=(ans+dp[act[verOfB]]+verOfB-verOfA)%mod;
	}
	if (leftSonB[verOfB]!=-1) dfsB(leftSonA[verOfB],leftSonB[verOfB]);
	if (rightSonB[verOfB]!=-1) dfsB(rightSonA[verOfB],rightSonB[verOfB]);
}

void init() {
	memset(leftSonA,-1,sizeof(leftSonA));
	memset(rightSonA,-1,sizeof(rightSonA));
	memset(leftSonB,-1,sizeof(leftSonB));
	memset(rightSonB,-1,sizeof(rightSonB));
}

int main() {
	init();
	read(n);
	rep(i,0,n) {
		read(a[i]); a[i]--;
		if (a[i]==-2) {
			rootA=i;
			continue;
		}
		if (a[i]>i) leftSonA[a[i]]=i;
		else rightSonA[a[i]]=i;
	}
	rep(i,0,n) {
		read(b[i]); b[i]--;
		if (b[i]==-2) {
			rootB=i;
			continue;
		}
		if (b[i]>i) leftSonB[b[i]]=i;
		else rightSonB[b[i]]=i;
	}
	dfsB(rootA,rootB);
	printf("%d\n",ans);
}