#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define sz size()
#define all(a) a.begin(),a.end()
#define SL(n) scanf("%lld",&n)
#define PL(n) printf("%lld",n)
#define fill(a, x) memset(a,x,sizeof(a));
#define mod 1000000007
using namespace std;
typedef long long LL;
typedef vector < LL> VL;
typedef map < LL, LL> ML;
typedef pair< LL, LL> PL;
typedef vector < pair < LL, LL> > VPL;
class Powerit{
public :
LL Power( LL base, LL expo, LL M) {
LL Ans = 1 ;
while ( expo > 0 ) {
if ( expo% 2 == 1 ) {
Ans = ( Ans* base) % M;
}
expo >>= 1 ;
base = ( base* base) % M;
}
return Ans% M;
}
LL Cal( LL n, LL K, LL m) {
LL M = ( ( LL) n * ( LL) m) ;
LL Temp = Power( 2 , K, M- 1 ) ;
LL Ans = Power( n, Temp, M) ;
Ans = ( LL) Ans/ n;
return ( LL) Ans;
}
int calc( LL N, LL K, LL M) {
LL Ans = 0 ;
for ( LL n= 1 ; n<= N; ++ n) {
Ans + = Cal( n, K, M) ;
Ans % = M;
}
return ( int ) ( Ans% M) ;
}
} ;
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgbXAgbWFrZV9wYWlyCiNkZWZpbmUgZmYgZmlyc3QKI2RlZmluZSBzcyBzZWNvbmQKI2RlZmluZSBzeiBzaXplKCkKI2RlZmluZSBhbGwoYSkgIGEuYmVnaW4oKSxhLmVuZCgpIAojZGVmaW5lIFNMKG4pIHNjYW5mKCIlbGxkIiwmbikKI2RlZmluZSBQTChuKSBwcmludGYoIiVsbGQiLG4pCiNkZWZpbmUgZmlsbChhLCB4KSBtZW1zZXQoYSx4LHNpemVvZihhKSk7CiNkZWZpbmUgbW9kIDEwMDAwMDAwMDcKCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnR5cGVkZWYgbG9uZyBsb25nIExMOwp0eXBlZGVmIHZlY3RvciA8TEw+IFZMOwp0eXBlZGVmIG1hcCA8TEwsIExMPiBNTDsKdHlwZWRlZiBwYWlyPExMLCBMTD4gUEw7CnR5cGVkZWYgdmVjdG9yIDxwYWlyIDxMTCwgTEw+ID4gVlBMOwoKY2xhc3MgUG93ZXJpdHsKICAgIHB1YmxpYzoKICAgICAgICBMTCBQb3dlcihMTCBiYXNlLCBMTCBleHBvLCBMTCBNKXsKICAgICAgICAgICAgTEwgQW5zID0gMTsKICAgICAgICAgICAgd2hpbGUoZXhwbyA+IDApewogICAgICAgICAgICAgICAgaWYoZXhwbyUyID09IDEpewogICAgICAgICAgICAgICAgICAgIEFucyA9IChBbnMqYmFzZSklTTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGV4cG8gPj49IDE7CiAgICAgICAgICAgICAgICBiYXNlID0gKGJhc2UqYmFzZSklTTsKICAgICAgICAgICAgfQogICAgICAgICAgICByZXR1cm4gQW5zJU07CiAgICAgICAgfQogICAgICAgIExMIENhbChMTCBuLCBMTCBLLCBMTCBtKXsKICAgICAgICAgICAgTEwgTSA9ICgoTEwpbiAqIChMTCltKTsKICAgICAgICAgICAgTEwgVGVtcCA9IFBvd2VyKDIsIEssIE0tMSk7CiAgICAgICAgICAgIExMIEFucyA9IFBvd2VyKG4sIFRlbXAsIE0pOwogICAgICAgICAgICBBbnMgPSAoTEwpQW5zL247CiAgICAgICAgICAgIHJldHVybiAoTEwpQW5zOwogICAgICAgIH0KICAgICAgICBpbnQgY2FsYyhMTCBOLCBMTCBLLCBMTCBNKXsKICAgICAgICAgICAgTEwgQW5zID0gMDsKICAgICAgICAgICAgZm9yKExMIG49MTtuPD1OOysrbil7CiAgICAgICAgICAgICAgICBBbnMgKz0gQ2FsKG4sIEssIE0pOwogICAgICAgICAgICAgICAgQW5zICU9IE07CiAgICAgICAgICAgIH0KICAgICAgICAgICAgcmV0dXJuIChpbnQpKEFucyVNKTsKICAgICAgICB9Cn07