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
#include <iostream>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <set>
#include <map>
#include <utility>
#include <queue>
#include <vector>
#include <string>
#include <cstring>

#define REP(a,n) for (int a = 0; a<(n); ++a)
#define FOR(a,b,c) for (int a = (b); a<=(c); ++a)
#define FORD(a,b,c) for (int a = (b); a>=(c); --a)
#define FOREACH(a,v) for (auto a : v)

#define MP make_pair
#define PB push_back

template<class T> inline int size(const T&t) { return t.size(); }

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<string> vs;
typedef long long LL;

///////////////////////////////

#define MOD 1'000'000'007

LL suma = 0;

int drzewo[2][500001][2];

#define src drzewo[0]
#define trg drzewo[1]

void prostuj_lewe_do(int lst, int &ile_nad, int &old_korz, int new_korz);
void napraw_prawe(int fst, int ile_nad, int old_korz, int new_korz);
void napraw_lewe(int lst, int ile_nad, int old_korz, int new_korz);

void prostuj_prawe_do(int fst, int &ile_nad, int &old_korz, int new_korz) {
  while (new_korz > fst + ile_nad - 1) {
    int ile_le = 0;
    int korz_le = src[old_korz][0];
    prostuj_lewe_do(old_korz - 1, ile_le, korz_le, fst + ile_nad);
    assert(!korz_le);
    suma += ile_le;
    ile_nad += ile_le + 1;
    assert(fst + ile_nad - 1 == old_korz);
    old_korz = src[old_korz][1];
  }
}

void prostuj_lewe_do(int lst, int &ile_nad, int &old_korz, int new_korz) {
  while (new_korz < lst - (ile_nad - 1)) {
    int ile_pr = 0;
    int korz_pr = src[old_korz][1];
    prostuj_prawe_do(old_korz + 1, ile_pr, korz_pr, lst - ile_nad);
    assert(!korz_pr);
    suma += ile_pr;
    ile_nad += ile_pr + 1;
    assert(lst - (ile_nad - 1) == old_korz);
    old_korz = src[old_korz][0];
  }
}

void napraw(int old_korz, int new_korz) {
  if (!new_korz) 
    return;
  if (new_korz == old_korz) {
    napraw(src[old_korz][0], trg[new_korz][0]);
    napraw(src[old_korz][1], trg[new_korz][1]);
  }
  else
  if (new_korz > old_korz) {
    int ile_pr = 0;
    int korz_pr = src[old_korz][1];
    prostuj_prawe_do(old_korz + 1, ile_pr, korz_pr, new_korz);
    int rot = new_korz - old_korz;
    suma += rot;
    napraw_lewe(new_korz - 1, rot, src[old_korz][0], trg[new_korz][0]);
    napraw_prawe(new_korz + 1, ile_pr - rot, korz_pr, trg[new_korz][1]);
  }
  else {
    int ile_le = 0;
    int korz_le = src[old_korz][0];
    prostuj_lewe_do(old_korz - 1, ile_le, korz_le, new_korz);
    int rot = old_korz - new_korz;
    suma += rot;
    napraw_lewe(new_korz - 1, ile_le - rot, korz_le, trg[new_korz][0]);
    napraw_prawe(new_korz + 1, rot, src[old_korz][1], trg[new_korz][1]);
  }
}

void napraw_prawe(int fst, int ile_nad, int old_korz, int new_korz) {
  if (!ile_nad) {
    napraw(old_korz, new_korz);
    return;
  }
  prostuj_prawe_do(fst, ile_nad, old_korz, new_korz);
  int rot = new_korz - fst;
  suma += rot;
  napraw_lewe(new_korz - 1, rot, 0, trg[new_korz][0]);
  napraw_prawe(new_korz + 1, ile_nad - rot - 1, old_korz, trg[new_korz][1]);
}

void napraw_lewe(int lst, int ile_nad, int old_korz, int new_korz) {
  if (!ile_nad) {
    napraw(old_korz, new_korz);
    return;
  }
  prostuj_lewe_do(lst, ile_nad, old_korz, new_korz);
  int rot = lst - new_korz;
  suma += rot;
  napraw_lewe(new_korz - 1, ile_nad - rot - 1, old_korz, trg[new_korz][0]);
  napraw_prawe(new_korz + 1, rot, 0, trg[new_korz][1]);
}

int main() {
  std::ios::sync_with_stdio(false);
  int N;
  cin >> N;
  int korz[2];
  REP(d, 2)
    FOR(a, 1, N) {
      int p;
      cin >> p;
      if (p < 0)
        korz[d] = a;
      else
        drzewo[d][p][a > p] = a;
    }
  napraw(korz[0], korz[1]);
  cout << suma % MOD << endl;
}