#include <bits/stdc++.h> using namespace std ; #define ll long long #define MOD (ll)(1000000000000000009) ll inv ( ll a , ll mod ){ ll r = mod ; ll nr = a ; ll t = 0 ; ll nt = 1 ; ll tmp ; while ( nr != 0 ){ ll q = r / nr ; tmp = nt ; nt = t - q * nt ; t = tmp ; tmp = nr ; nr = r - q * nr ; r = tmp ; } if ( r > 1 ) return - 1 ; // no inverse if ( t < 0 ) t += mod ; return t ; } ll f ( ll a , ll n , ll mod ){ ll res = a , ans = 0 ; while ( n ){ if ( n % 2 ) ans = ( ans + res ) % mod ; res = ( res + res ) % mod ; n /= 2 ; } return ans ; } ll po ( ll a , ll n , ll mod ){ ll res = a , ans = 1 ; while ( n ){ if ( n % 2 ) ans = f ( ans , res , mod ); res = f ( res , res , mod ); n /= 2 ; } return ans ; } int main (){ ll x , y , z , m , dem = 0 , res1 , res2 , res , tmp