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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include <bits/stdc++.h>

using namespace std;

typedef long long int LL;

const int N = 5e5 + 7;
const int MX = 1e9 + 7;

int n;
int start_root[2];
int Left[2][N], Right[2][N];

void read() {
	scanf("%d", &n);
	for(int t = 0; t < 2; ++t) {
		for(int i = 1; i <= n; ++i)
			Left[t][i] = Right[t][i] = -1;
		
		for(int i = 1; i <= n; ++i) {
			int cur;
			scanf("%d", &cur);
			
			if(cur == -1)
				start_root[t] = i;
			else if(cur < i)
				Right[t][cur] = i;
			else
				Left[t][cur] = i;
				
		}
	}
}

void add(int &a, int b) {
	a += b;
	if(a >= MX)
		a -= MX;
}

int make_path(int root, bool type, int &sz) {
	int ret = 0;
	sz = 1;

	if(Left[0][root] != -1) {
		int left_size = 0;
		add(ret, make_path(Left[0][root], 1, left_size));
		
		if(!type)
			add(ret, left_size);
		sz += left_size;
	}
	
	if(Right[0][root] != -1) {
		int right_size = 0;
		add(ret, make_path(Right[0][root], 0, right_size));
		
		if(type)
			add(ret, right_size);
		sz += right_size;
	}

	return ret;
}

int solve(int cur_root, int need_root, int path, int from, int to) {
	if(from == to)
		return 0;
	
	/* Roots matches */
	if(cur_root == need_root) {
		if(path) {
			if(cur_root == from)
				return solve(cur_root + 1, Right[1][need_root], path - 1, from + 1, to);
			return solve(cur_root - 1, Left[1][need_root], path - 1, from, to - 1);
		}
		
		int ret = 0;
		if(cur_root > from)
			add(ret, solve(Left[0][cur_root], Left[1][need_root], 0, from, cur_root - 1));
		if(cur_root < to)
			add(ret, solve(Right[0][cur_root], Right[1][need_root], 0, cur_root + 1, to));
		return ret;
	}
	
	/* Root in the left subtree */
	if(need_root < cur_root) {
		int ret = 0;
		int left_path = 0;
		int right_path = 0;

		/* Move the maximums to the root as long as possible */
		while(cur_root > need_root) {
			/* If the is job already done */
			if(path >= cur_root - need_root) {
				add(ret, cur_root - need_root);

				left_path = path - (cur_root - need_root) - 1;
				right_path += cur_root - need_root - 1;
				
				if(need_root > from)
					add(ret, solve(left_path == -1 ? Left[0][need_root] : need_root - 1, Left[1][need_root], max(left_path, 0), from, need_root - 1));
				add(ret, solve(need_root + 1, Right[1][need_root], right_path, need_root + 1, to));
				return ret;
			}
			
			cur_root -= path;
			right_path += path;
			add(ret, path);

			/* Create next path */
			if(Left[0][cur_root] + 1 < cur_root)
				add(ret, make_path(Right[0][Left[0][cur_root]], 0, path));
			else
				path = 0;
			add(ret, path++);
		}
	}
	
	/* Root in the right subtree */
	if(cur_root < need_root) {
		int ret = 0;
		int left_path = 0;
		int right_path = 0;
		
		/* If the job is already done */
		while(cur_root < need_root) {
			if(path >= need_root - cur_root) {
				add(ret, need_root - cur_root);

				left_path += need_root - cur_root - 1;
				right_path = path - (need_root - cur_root) - 1;
				
				add(ret, solve(need_root - 1, Left[1][need_root], left_path, from, need_root - 1));
				if(need_root < to)
					add(ret, solve(right_path == -1 ? Right[0][need_root] : need_root + 1, Right[1][need_root], max(right_path, 0), need_root + 1, to));
				return ret;
			}
		
			cur_root += path;
			left_path += path;
			add(ret, path);
			
			/* Create next path */
			if(cur_root + 1 < Right[0][cur_root])
				add(ret, make_path(Left[0][Right[0][cur_root]], 1, path));
			else
				path = 0;
			add(ret, path++);
		}
	}
	
	return 0;
}

int main() {
	read();
	int ans = solve(start_root[0], start_root[1], 0, 1, n);
	printf("%d\n", ans);
	return 0;
}