/*
使用归纳法可证得，solve(1)=(cnt[1]-1)!/(cnt[2]*cnt[3]*cnt[4]*……);
*/
#include<iostream>
using namespace std;
const int N = 510000;
int n, mol;
int rudu[ N ], cnt[ N ], per[ N ];
int prim[ 10 ], prim_k, fac_num[ 10 ];
int que[ N ], top, bot;
void build()
{
int i, tmp;
scanf("%d%d",&n,&mol);
memset( rudu , 0 , sizeof( rudu ));
per[0] = per[1] = 0;
for ( i = 2 ; i <= n ; i ++ )
{
scanf("%d",&tmp);
per[ i ] = tmp ;
rudu[ tmp ] ++ ;
}
}
void init()
{
int i, t;
cnt[ 0 ] = 0;
for ( i = n, top = bot = 0 ; i > 0 ; i -- )
{
if( rudu[ i ] == 0 )
que[ top ++ ] = i;
cnt[ i ] = 1 ;
}
while( bot != top )
{
t = que[ bot ++ ];
rudu[ per[ t ] ] -- ;
cnt [ per[ t ] ] += cnt[ t ];
if( rudu[ per[ t ] ] == 0 )
que[ top ++ ] = per[ t ];
}
}
void prime_fac( const int & mol )
{
int t = mol, i;
prim_k = 0;
memset( fac_num, 0, sizeof( fac_num));
for ( i = 2 ; i * i <= mol ; i ++ )
{
if( t % i == 0 )
{
prim[ prim_k ++ ] = i;
}
while( t % i == 0 )
{
t /= i;
}
}
if( t != 1 )
prim[ prim_k ++ ] = t ;
}
int fac_down( int m, int flag )
{
int i;
for ( i = 0 ; i < prim_k ; i ++ )
{
while( m % prim[i] == 0 )
{
fac_num[ i ] += flag ;
m /= prim[ i ];
}
}
return m ;
}
int ext_gcd(int a,int b,int &x,int &y)
{
if( b == 0 )
{
x = 1, y = 0;
return a;
}
else
{
int d = ext_gcd( b, a%b, x, y );
int t = x;
x = y;
y = t - a/b*y;
return d;
}
}
int ni( int a,int b)
{
int x, y;
ext_gcd( a, b, x, y );
return ((x%b+b)%b);
}
// n 是已分解的数
int ext_mult(int n,int m,const int & mol )
{
m = fac_down( m, 1 );
return 1ll * n * m % mol;
}
int ext_dive( int n, int m, const int & mol )
{
m = fac_down( m, -1 );
return 1ll * n * ni( m, mol ) % mol;
}
int mol_pow( int n, int m )
{
int t = n, ans = 1;
while( m )
{
if( m & 1 )
{
ans = 1ll * ans * t % mol;
}
t = 1ll * t * t % mol;
m >>= 1;
}
return ans;
}
void solve()
{
prime_fac( mol );
int ans = 1, i;
for ( i = n - 1 ; i >= 1 ; i -- )
{
ans = ext_mult( ans, i, mol );
ans = ext_dive( ans, cnt[i+1], mol );
}
for ( i = 0 ; i < prim_k ; i ++ )
{
ans = 1ll * ans * mol_pow( prim[i], fac_num[i] ) % mol ;//这步不需要带因子的乘法
}
cout<<ans<<endl;
}
int main()
{
int i, j, k;
int test;
scanf("%d",&test);
while( test -- )
{
build();
init();
solve();
}
return 0;
}
posted on 2009-08-17 12:09
Huicpc217 阅读(238)
评论(1) 编辑 收藏 引用