#include<bits/stdc++.h> using namespace std; #define ll long long const int MAXN=1e6+6; const ll mod=1e9+7; int n,m,p; vector<int>g[MAXN]; vector<int>t; bool vis[MAXN]; void dfs(int u) { vis[u]=1; for(auto v:g[u]) { if(vis[v]==0) { dfs(v); } } t.push_back(u); } int a[MAXN]; int where[MAXN]; int w1[MAXN]; ll dp[MAXN]; int main() { cin>>n>>m>>p; for(int i=1;i<=p;i++) { cin>>a[i]; } for(int i=0;i<m;i++) { int x,y; cin>>x>>y; g[x].push_back(y); } for(int i=1;i<=n;i++) { if(vis[i]==0) { dfs(i); } } reverse(t.begin(),t.end()); for(int i=0;i<t.size();i++)where[t[i]]=i; /*for(int i=2;i<=p;i++) { if(where[i-1]>where[i]) { cout<<"0\n"; return 0; } }*/ ll ans=1; dp[1]=1ll; //cout<<a[1]<<" "<<where[a[1]]<<endl; for(int j=where[1];j<=where[a[1]];j++) { for(auto v:g[t[j]]) { if(where[v]>where[a[1]])continue; //cout<<t[j]<<"->"<<v<<endl; dp[v]+=dp[t[j]]; dp[v]%=mod; } } ans*=dp[a[1]]; //cout<<ans<<endl; for(ll i=2;i<=p;i++) { dp[a[i-1]]=1; for(int j=where[a[i-1]];j<=where[a[i]];j++) { for(auto v:g[t[j]]) { if(where[v]>where[a[i]])continue; dp[v]+=dp[t[j]]; dp[v]%=mod; } } ans*=dp[a[i]]; ans%=mod; //cout<<ans<<endl; } dp[a[p]]=1; for(int j=where[a[p]];j<=where[n];j++) { for(auto v:g[t[j]]) { if(where[v]>where[n])continue; dp[v]+=dp[t[j]]; dp[v]%=mod; } } ans*=dp[n]; ans%=mod; cout<<ans<<endl; return 0; } /* 6 9 3 3 5 6 1 3 1 3 1 2 2 3 2 4 3 4 3 5 4 5 5 6 */

shell.cpp: In function 'int main()':
shell.cpp:47:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for(int i=0;i<t.size();i++)where[t[i]]=i;
      |              ~^~~~~~~~~