#include <iostream>
#include <vector>
#include <set>
using namespace std;


class CandyCupRunningCompetition{
    public:
    int n,m;
    vector<int> adj[4000];
    vector<int> cst[4000];
    long long p3[4003];
    long long sol=0;
    long long mod=1000000007;
    int grp[4003];
    int fnd(int x){
        if(grp[x]!=x){
            grp[x]=fnd(grp[x]);
        }
        return grp[x];
    }
    void uni(int x,int y,int ii){
        int X=fnd(x);
        int Y=fnd(y);
        int _0=fnd(0);
        int _n=fnd(n-1);
        if(_0==X && _n==Y){
            sol+=p3[ii];
            sol%=mod;
        } else if(_0==Y && _n==X){
            sol+=p3[ii];
            sol%=mod;
        } else {
            grp[X]=Y;
        }
    }
    int findMaximum(int N, vector <int> A, vector <int> B){
        m=A.size();
        n=N;
        p3[0]=1;
        grp[0]=0;
        for(int i=1;i<4000;i++){
            p3[i]=(p3[i-1]*3)%mod;
            grp[i]=i;
        }
        for(int i=m-1;i>=0;i--){
            uni(A[i],B[i],i);
        }
        return sol;
    }
};