#include <cstdio>

using namespace std;

const int MOD = 1e4 + 7 ;

inline int fast_exp ( int x , int y )
{
    int ans = 1 , p = x ;

    while ( y )
    {
        if ( y & 1 )
            ans = ( ans * p ) % MOD ;
        p = ( p * p ) % MOD ;
        y = y >> 1 ;
    }

    return ans ;
}

int main()
{
    freopen ( "matrice5.in" , "r" , stdin ) ;
    freopen ( "matrice5.out" , "w" , stdout ) ;

    int t , n , m , p , k , i ;

    scanf ( "%d" , & t ) ;

    for ( i = 1 ; i <= t ; ++ i )
    {
        scanf ( "%d%d%d%d" , & n , & m , & p , & k ) ;

        printf ( "%d\n" , ( fast_exp ( k , ( n - 1 ) * ( m - 1 ) ) * fast_exp ( p , m * n ) ) % MOD ) ;
    }

    return 0;
}