// 誤解法（愚直オーバーフローO(T N_max)解）チェック
#pragma GCC optimize ( "O3" )
#pragma GCC optimize( "unroll-loops" )
#pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )
#include <iostream>
#include <stdio.h>
#include <stdint.h>
#include <cassert>
using namespace std;

using ll = long long;

#define MAIN main
#define TYPE_OF( VAR ) remove_const<remove_reference<decltype( VAR )>::type >::type
#define UNTIE ios_base::sync_with_stdio( false ); cin.tie( nullptr ) 
#define CEXPR( LL , BOUND , VALUE ) constexpr const LL BOUND = VALUE 
#define CIN( LL , A ) LL A; cin >> A 
#define ASSERT( A , MIN , MAX ) assert( MIN <= A && A <= MAX ) 
#define CIN_ASSERT( A , MIN , MAX ) CIN( TYPE_OF( MAX ) , A ); ASSERT( A , MIN , MAX ) 
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ )
#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES )
#define QUIT return 0 
#define RETURN( ANSWER ) cout << ( ANSWER ) << "\n"; QUIT 

template <typename T> inline T Absolute( const T& a ){ return a > 0 ? a : -a; }

template <typename T>
class TwoByTwoMatrix
{

public:
  // private:
  T m_M00;
  T m_M01;
  T m_M10;
  T m_M11;

public:
  inline TwoByTwoMatrix( const T& M00 , const T& M01 , const T& M10 , const T& M11 ) noexcept;
  inline TwoByTwoMatrix( const T& n = T() ) noexcept;
  inline TwoByTwoMatrix<T>& operator=( const TwoByTwoMatrix<T>& mat ) noexcept;
  inline TwoByTwoMatrix<T>& operator+=( const TwoByTwoMatrix<T>& mat );
  inline TwoByTwoMatrix<T>& operator*=( const TwoByTwoMatrix<T>& mat ) noexcept;

  inline TwoByTwoMatrix<T> operator*( const TwoByTwoMatrix<T>& mat );
  
};

template <typename T> inline TwoByTwoMatrix<T>::TwoByTwoMatrix( const T& M00 , const T& M01 , const T& M10 , const T& M11 ) noexcept : m_M00( M00 ) , m_M01( M01 ) , m_M10( M10 ) , m_M11( M11 ) {}
template <typename T> inline TwoByTwoMatrix<T>::TwoByTwoMatrix( const T& n ) noexcept : m_M00( n ) , m_M01() , m_M10() , m_M11( n ) {}

template <typename T> inline TwoByTwoMatrix<T>& TwoByTwoMatrix<T>::operator=( const TwoByTwoMatrix<T>& mat ) noexcept { if( &mat != this ){ m_M00 = mat.m_M00; m_M01 = mat.m_M01; m_M10 = mat.m_M10; m_M11 = mat.m_M11; } return *this; }

template <typename T> inline TwoByTwoMatrix<T>& TwoByTwoMatrix<T>::operator+=( const TwoByTwoMatrix<T>& mat ) { m_M00 += mat.m_M00; m_M01 += mat.m_M01; m_M10 += mat.m_M10; m_M11 += mat.m_M11; return *this; }
template <typename T> inline TwoByTwoMatrix<T>& TwoByTwoMatrix<T>::operator*=( const TwoByTwoMatrix<T>& mat ) noexcept { return operator=( *this * mat ); }

template <typename T> inline TwoByTwoMatrix<T> TwoByTwoMatrix<T>::operator*( const TwoByTwoMatrix<T>& mat ) { return TwoByTwoMatrix<T>( m_M00 * mat.m_M00 + m_M01 * mat.m_M10 , m_M00 * mat.m_M01 + m_M01 * mat.m_M11 , m_M10 * mat.m_M00 + m_M11 * mat.m_M10 , m_M10 * mat.m_M01 + m_M11 * mat.m_M11 ); }

inline int Solve()
{
  CEXPR( ll , bound_N , 1000000000000000000 );
  CIN_ASSERT( N , 1 , bound_N );
  CEXPR( ll , bound_B , 1000000000 );
  CIN_ASSERT( B , 1 , bound_B );
  CEXPR( ll , bound_Aij , 1000000000 );
  CEXPR( int , size , 2 );
  CIN_ASSERT( A00 , -bound_Aij , bound_Aij );
  CIN_ASSERT( A01 , -bound_Aij , bound_Aij );
  CIN_ASSERT( A10 , -bound_Aij , bound_Aij );
  CIN_ASSERT( A11 , -bound_Aij , bound_Aij );
  TwoByTwoMatrix<ll> A{ A00 , A01 , A10 , A11 };
  TwoByTwoMatrix<ll> A_power = A;
  TwoByTwoMatrix<ll> A_power_sum{};
  REPEAT( N ){
    A_power_sum += A_power;
    A_power *= A;
  }
  RETURN( Absolute( A_power_sum.m_M00 * A_power_sum.m_M11 - A_power_sum.m_M01 * A_power_sum.m_M10 ) % B );
}

int MAIN()
{
  UNTIE;
  CEXPR( int , bound_T , 1000 );
  CIN_ASSERT( T , 1 , bound_T );
  REPEAT( T ){
    Solve();
  }
  QUIT;
}