There are N towns numbered 1, 2, \cdots, N.

Some roads are planned to be built so that each of them connects two distinct towns bidirectionally. Currently, there are no roads connecting towns.

In the planning of construction, each town chooses one town different from itself and requests the following: roads are built so that the chosen town is reachable from itself using one or more roads.

These requests from the towns are represented by an array P_1, P_2, \cdots, P_N. If P_i = -1, it means that Town i has not chosen the request; if 1 \leq P_i \leq N, it means that Town i has chosen Town P_i.

Let K be the number of towns i such that P_i = -1. There are (N-1)^K ways in which the towns can make the requests. For each way to make requests, find the minimum number of roads needed to meet all the requests, and print the sum of those (N-1)^K numbers, modulo (10^9+7).

Constraints

* 2 \leq N \leq 5000
* P_i = -1 or 1 \leq P_i \leq N.
* P_i \neq i
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N
P_1 P_2 \cdots P_N


Output

For each way to make requests, find the minimum number of roads needed to meet all the requests, and print the sum of those (N-1)^K numbers, modulo (10^9+7).

Examples

Input

4
2 1 -1 3


Output

8


Input

2
2 1


Output

1


Input

10
2 6 9 -1 6 9 -1 -1 -1 -1


Output

527841
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define debug(x) cerr<<#x<<" = "<<x
#define sp <<"  "
#define el <<endl
#define fgx cerr<<" ---------------------------------------------- "<<endl
#define uint unsigned int 
#define ULL unsigned long long
#define DB long double
#define LDB long double
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define rint register int 
namespace IO{
	const int BS=(1<<23)+5; int Top=0;
	char Buffer[BS],OT[BS],*OS=OT,*HD,*TL,SS[20]; const char *fin=OT+BS-1;
	char Getchar(){if(HD==TL){TL=(HD=Buffer)+fread(Buffer,1,BS,stdin);} return (HD==TL)?EOF:*HD++;}
	void flush(){fwrite(OT,1,OS-OT,stdout),OS=OT;}
	void Putchar(char c){*OS++ =c;if(OS==fin)flush();}
	void write(int x){
		if(!x){Putchar('0');return;} if(x<0) x=-x,Putchar('-');
		while(x) SS[++Top]=x%10,x/=10;
		while(Top) Putchar(SS[Top]+'0'),--Top;
	}
	inline LL read(){
		LL nm=0; bool fh=true; char cw=getchar();
		for(;!isdigit(cw);cw=getchar()) fh^=(cw=='-');
		for(;isdigit(cw);cw=getchar()) nm=nm*10+(cw-'0');
		return fh?nm:-nm;
	}
} using namespace IO;
#define mod 1000000007
namespace CALC{
	inline int add(int x,int y){return (x+y>=mod)?(x+y-mod):(x+y);}
	inline int mns(int x,int y){return (x-y<0)?(x-y+mod):(x-y);}
	inline int mul(int x,int y){return (LL)x*(LL)y%mod;}
	inline void upd(int &x,int y){x=(x+y>=mod)?(x+y-mod):(x+y);}
	inline void dec(int &x,int y){x=(x-y<0)?(x-y+mod):(x-y);}
	inline int qpow(int x,LL sq){int res=1;for(;sq;sq>>=1,x=mul(x,x))if(sq&1)res=mul(res,x);return res;}
}using namespace CALC;
#define M 5020
int n,a[M],m,p[M],fs[M],nt[M],to[M],tmp;
int tg[M],sz[M],ot,ans,F[M],fac[M],pw[M];
inline void link(int x,int y){nt[tmp]=fs[x],fs[x]=tmp,to[tmp++]=y;}
inline void dfs(int x){
	tg[x]=-1,++sz[m];
	for(int i=fs[x];i!=-1;i=nt[i]) dfs(to[i]);
}
int TIM;
inline bool fd(int x){
	++TIM;
	while(!tg[x]) tg[x]=TIM,x=p[x]; if(tg[x]!=TIM||x==-1) return false;
	return true;
}
int main(){
	n=read(),memset(fs,-1,sizeof(fs)),fac[0]=pw[0]=1;
	for(int i=1;i<=n;i++) p[i]=read(),fac[i]=mul(i,fac[i-1]),pw[i]=mul(pw[i-1],n-1);
	for(int i=1;i<=n;i++) if(p[i]!=-1) link(p[i],i);
	for(int i=1;i<=n;i++) if(p[i]==-1) ++m,dfs(i);
	for(int i=1;i<=n;i++) if(fd(i)) ++ot;
//	debug(ot)el;
	ans=mul(mns(n,ot),qpow(n-1,m)),F[0]=1;
//	debug(ans)el;
	for(int i=1;i<=m;i++) for(int k=i-1;k>=0;--k) upd(F[k+1],mul(F[k],sz[i]));
	for(int i=2;i<=m;i++) dec(ans,mul(F[i],mul(pw[m-i],fac[i-1])));
	for(int i=1;i<=m;i++) dec(ans,mul(pw[m-1],sz[i]-1));
	printf("%d\n",ans);
	return 0;
}