#include<bits/stdc++.h>
// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
//------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
//Give shorthand names to data types using typedef.
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair< int , int > pii;
typedef vector< int > vi;
typedef vector< vi> vvi;
typedef vector< pii> vpii;
typedef vector< vpii> vvpii;
typedef pair< ll, ll> pll;
typedef vector< ll> vll;
typedef vector< vll> vvll;
typedef vector< pll> vpll;
typedef vector< vpll> vvpll;
typedef pair< ll,pair< ll,ll>> triplet;
// #define ordered_set tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update>
//------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
#define fo(i,n) for(int i=0;i<n;i++)
#define fo1(i,n) for(int i=1;i<=n;i++)
#define Fo(i,n) for(int i=n-1;i>=0;i--)
#define Fo1(i,n) for(int i=n;i>=1;i--)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define rep2(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define eb emplace_back
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define set_bits __builtin_popcountll
#define PI 3.1415926535897932384626
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
mt19937 rnd( ( unsigned int ) chrono:: steady_clock :: now ( ) .time_since_epoch ( ) .count ( ) ) ;
const int MOD = 1e9 + 7 ;
const int MOD1 = 998244353 ;
const int MOD3 = 1610612741 ;
/* Alternate Prime nos where probability of collision is less for hashing for MOD3:
long long:
1000000000039
2000000000003
3000000000013
4000000000039
int:
1610612741(currently used).
*/
const ll INF = 1e18 + 9 ;
const ll NINF = - 1e18 - 9 ;
#define deb(x) cerr << #x <<" "; _print(x); cerr << endl;
template < class T> void _print( T x) { cerr << x; }
template < class T, class V> void _print( pair < T, V> p) { cerr << "{" ; _print( p.F ) ; cerr << "," ; _print( p.S ) ; cerr << "}" ; }
template < class T> void _print( vector < T> v) { cerr << "[ " ; for ( T i : v) { _print( i) ; cerr << " " ; } cerr << "]" ; }
template < class T> void _print( set < T> v) { cerr << "[ " ; for ( T i : v) { _print( i) ; cerr << " " ; } cerr << "]" ; }
template < class T> void _print( multiset < T> v) { cerr << "[ " ; for ( T i : v) { _print( i) ; cerr << " " ; } cerr << "]" ; }
template < class T, class V> void _print( map < T, V> v) { cerr << "[ " ; for ( auto i : v) { _print( i) ; cerr << " " ; } cerr << "]" ; }
vi primes;
vi spf;
vector< bool > prime;
//------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
ll gcd( ll a, ll b) { if ( b > a) { return gcd( b, a) ; } if ( b == 0 ) { return a; } return gcd( b, a % b) ; }
ll mpow( ll base, ll exp , ll mod) { base % = mod; ll result = 1 ; while ( exp > 0 ) { if ( exp & 1 ) result = ( result * base) % mod; base = ( base * base) % mod; exp >>= 1 ; } return result; }
//Use when 'a' and 'b' are less than mod,but their addition can go beyond mod.
ll mAdd( ll a, ll b , ll mod) { return ( a + b >= mod ? a + b - mod : a + b) ; }
void extendgcd( ll a, ll b, ll* v) { if ( b == 0 ) { v[ 0 ] = 1 ; v[ 1 ] = 0 ; v[ 2 ] = a; return ; } extendgcd( b, a % b, v) ; ll x = v[ 1 ] ; v[ 1 ] = v[ 0 ] - v[ 1 ] * ( a / b) ; v[ 0 ] = x; return ; } //pass an arry of size1 3
ll mminv( ll a, ll b) { ll arr[ 3 ] ; extendgcd( a, b, arr) ; return arr[ 0 ] ; } //for non prime b
ll mminvprime( ll a, ll b) { return mpow( a, b - 2 , b) ; }
bool revsort( ll a, ll b) { return a > b; }
void swap( ll & x, ll & y) { int temp = x; x = y; y = temp; }
ll combination( ll n, ll r, ll m, ll * fact, ll * ifact) { ll val1 = fact[ n] ; ll val2 = ifact[ n - r] ; ll val3 = ifact[ r] ; return ( ( ( val1 * val2) % m) * val3) % m; }
void google( int t) { cout << "Case #" << t << ": " ; }
ll mod_add( ll a, ll b, ll m) { a = a % m; b = b % m; return ( ( ( a + b) % m) + m) % m; }
ll mod_mul( ll a, ll b, ll m) { a = a % m; b = b % m; return ( ( ( a * b) % m) + m) % m; }
ll mod_sub( ll a, ll b, ll m) { a = a % m; b = b % m; return ( ( ( a - b) % m) + m) % m; }
ll mod_div( ll a, ll b, ll m) { a = a % m; b = b % m; return ( mod_mul( a, mminvprime( b, m) , m) + m) % m; } //only for prime m
ll phin( ll n) { ll number = n; if ( n % 2 == 0 ) { number / = 2 ; while ( n % 2 == 0 ) n / = 2 ; } for ( ll i = 3 ; i <= sqrt ( n) ; i + = 2 ) { if ( n % i == 0 ) { while ( n % i == 0 ) n / = i; number = ( number / i * ( i - 1 ) ) ; } } if ( n > 1 ) number = ( number / n * ( n - 1 ) ) ; return number; }
vector< long long > computeHash( string & s) { ll str_len= s.length ( ) ; ll p_pow[ str_len] ; ll p= 123 ; p_pow[ 0 ] = 1 ; for ( int i= 1 ; i< str_len; i++ ) p_pow[ i] = ( p_pow[ i- 1 ] * p) % MOD3; vector< long long > hash( str_len+ 1 ) ; hash[ 0 ] = 0 ; for ( int i= 1 ; i<= str_len; i++ ) hash[ i] = ( hash[ i- 1 ] + ( ( s[ i- 1 ] - 'a' + 1 ) * p_pow[ i- 1 ] ) % MOD3 ) % MOD3; return hash; }
vector< int > makeZarray( string s) { int n = s.length ( ) ; vector< int > z( n) ; int l= 0 ,r= 0 ; for ( int i= 1 ; i< n; i++ ) { if ( i<= r) z[ i] = min( z[ i- l] ,r- i+ 1 ) ; while ( i+ z[ i] < n && s[ z[ i] ] == s[ i+ z[ i] ] ) z[ i] ++ ; if ( i+ z[ i] - 1 > r) l= i , r= i+ z[ i] - 1 ; } return z; }
//O(nloglogn)
void sieve( int n) { prime.assign ( n+ 1 ,true ) ; prime[ 0 ] = 0 ; prime[ 1 ] = 0 ; for ( int i = 2 ; i <= n; i++ ) if ( prime[ i] == 1 ) { primes.eb ( i) ; for ( ll j = ( ll) i * i; j <= n; j + = i) { if ( prime[ j] ) prime[ j] = 0 ; } } }
//O(nloglogn) Max value of n=1e6.
void find_spf( int n) { n = max( n,1 ) ; spf.assign ( n+ 1 ,0 ) ; prime.assign ( n+ 1 ,true ) ; prime[ 0 ] = prime[ 1 ] = false ; int i; for ( i= 2 ; i<= n; i++ ) { if ( prime[ i] ) { primes.eb ( i) ; spf[ i] = i; for ( ll j= ( ll) i* i; j<= n; j+ = i) { if ( prime[ j] ) { prime[ j] = false ; spf[ j] = i; } } } } }
//O(log2n) time at max. Before running this , Run sieve(if n larger than 1e6) or find_spf() if n<=1e6,both upto sqrt(n).
vpll prime_factorize( ll n) { vpll result; if ( n < spf.size ( ) ) { while ( n! = 1 ) { ll fact = spf[ n] ; ll exp = 0 ; do { n/ = fact; exp ++ ; } while ( n% fact== 0 ) ; result.eb ( fact,exp ) ; } return result; } else { for ( auto p : primes) { if ( p* p > n) break ; if ( n % p== 0 ) { result.emplace_back ( p, 0 ) ; do { n / = p; result.back ( ) .second ++ ; } while ( n % p == 0 ) ; } } if ( n> 1 ) result.eb ( n,1 ) ; return result; } }
ll sumprimeExp( ll n) { vpll prime_factors = prime_factorize( n) ; ll ans= 0 ; for ( auto p : prime_factors) { ans+ = p.second ; } return ans; }
//---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
ll n;
ll helperEven( ll k,ll sum) {
if ( k== 0 ) return 1 ;
ll val1 = ( sum* helperEven( k- 1 ,sum) ) % MOD;
ll val2 = mpow( 2 ,n* ( k- 1 ) ,MOD) ;
return ( val1 + val2) % MOD;
}
ll helperOdd( ll k,ll sum) {
if ( k== 0 ) return 1 ;
ll val1 = ( sum* helperEven( k- 1 ,sum) ) % MOD;
return val1;
}
int32_t main( )
{
fast_io;
int t;
cin >> t;
ll Max = 2 * 1e5 + 1 ;
ll fact[ Max] ,ifact[ Max] ;
fact[ 0 ] = 1 ; ifact[ 0 ] = 1 ;
for ( ll i= 1 ; i<= Max- 1 ; i++ ) {
fact[ i] = ( fact[ i- 1 ] * i) % MOD;
ifact[ i] = mminvprime( fact[ i] ,MOD) ;
}
while ( t-- )
{
ll k; cin >> n>> k;
ll sum = 0 ;
if ( n% 2 == 0 ) {
for ( ll i= 0 ; i<= n- 2 ; i+ = 2 ) {
sum = ( sum + combination( n,i,MOD,fact,ifact) ) % MOD;
}
cout << helperEven( k,sum) ;
}
else {
for ( ll i= 0 ; i<= n- 1 ; i+ = 2 ) {
sum = ( sum + combination( n,i,MOD,fact,ifact) ) % MOD;
}
cout << helperOdd( k,( sum+ 1 ) % MOD) ;
}
cout << endl;
}
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KLy8gI2luY2x1ZGU8ZXh0L3BiX2RzL2Fzc29jX2NvbnRhaW5lci5ocHA+Ci8vICNpbmNsdWRlPGV4dC9wYl9kcy90cmVlX3BvbGljeS5ocHA+CnVzaW5nICBuYW1lc3BhY2Ugc3RkOwovLyB1c2luZyBuYW1lc3BhY2UgX19nbnVfcGJkczsKCi8vLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCi8vR2l2ZSBzaG9ydGhhbmQgbmFtZXMgdG8gZGF0YSB0eXBlcyB1c2luZyB0eXBlZGVmLgp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKdHlwZWRlZiB1bnNpZ25lZCBsb25nIGxvbmcgdWxsOwp0eXBlZGVmIGxvbmcgZG91YmxlIGxkOwp0eXBlZGVmIHBhaXI8aW50LCBpbnQ+ICBwaWk7CnR5cGVkZWYgdmVjdG9yPGludD4gdmk7CnR5cGVkZWYgdmVjdG9yPHZpPiB2dmk7CnR5cGVkZWYgdmVjdG9yPHBpaT4gdnBpaTsKdHlwZWRlZiB2ZWN0b3I8dnBpaT4gdnZwaWk7CnR5cGVkZWYgcGFpcjxsbCwgbGw+IHBsbDsKdHlwZWRlZiB2ZWN0b3I8bGw+ICB2bGw7CnR5cGVkZWYgdmVjdG9yPHZsbD4gdnZsbDsKdHlwZWRlZiB2ZWN0b3I8cGxsPiB2cGxsOwp0eXBlZGVmIHZlY3Rvcjx2cGxsPiB2dnBsbDsKdHlwZWRlZiBwYWlyPGxsLHBhaXI8bGwsbGw+PiB0cmlwbGV0OwovLyAjZGVmaW5lIG9yZGVyZWRfc2V0IHRyZWU8cGFpcjxpbnQsaW50PiwgbnVsbF90eXBlLCBsZXNzPHBhaXI8aW50LGludD4+LCByYl90cmVlX3RhZywgdHJlZV9vcmRlcl9zdGF0aXN0aWNzX25vZGVfdXBkYXRlPgoKLy8tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KI2RlZmluZSBmbyhpLG4pIGZvcihpbnQgaT0wO2k8bjtpKyspCiNkZWZpbmUgZm8xKGksbikgZm9yKGludCBpPTE7aTw9bjtpKyspCiNkZWZpbmUgRm8oaSxuKSBmb3IoaW50IGk9bi0xO2k+PTA7aS0tKQojZGVmaW5lIEZvMShpLG4pIGZvcihpbnQgaT1uO2k+PTE7aS0tKQojZGVmaW5lIHJlcChpLGEsYikgZm9yKGludCBpPWE7aTw9YjtpKyspCiNkZWZpbmUgcmVwMihpLGEsYikgZm9yKGludCBpPWE7aT49YjtpLS0pCgojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIGViIGVtcGxhY2VfYmFjawojZGVmaW5lIEYgZmlyc3QKI2RlZmluZSBTIHNlY29uZAojZGVmaW5lIGFsbCh4KSAoeCkuYmVnaW4oKSwgKHgpLmVuZCgpCiNkZWZpbmUgc2V0X2JpdHMgX19idWlsdGluX3BvcGNvdW50bGwKCiNkZWZpbmUgUEkgMy4xNDE1OTI2NTM1ODk3OTMyMzg0NjI2CgojZGVmaW5lIGZhc3RfaW8gaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7Y2luLnRpZShOVUxMKQptdDE5OTM3IHJuZCgodW5zaWduZWQgaW50KSBjaHJvbm86OnN0ZWFkeV9jbG9jazo6bm93KCkudGltZV9zaW5jZV9lcG9jaCgpLmNvdW50KCkpOwoKY29uc3QgaW50IE1PRCA9IDFlOSs3Owpjb25zdCBpbnQgTU9EMSA9IDk5ODI0NDM1MzsKY29uc3QgaW50IE1PRDMgPSAxNjEwNjEyNzQxOwovKiBBbHRlcm5hdGUgUHJpbWUgbm9zIHdoZXJlIHByb2JhYmlsaXR5IG9mIGNvbGxpc2lvbiBpcyBsZXNzIGZvciBoYXNoaW5nIGZvciBNT0QzOgogICAgbG9uZyBsb25nOgogICAgMTAwMDAwMDAwMDAzOQogICAgMjAwMDAwMDAwMDAwMwogICAgMzAwMDAwMDAwMDAxMwogICAgNDAwMDAwMDAwMDAzOQogICAgaW50OgogICAgMTYxMDYxMjc0MShjdXJyZW50bHkgdXNlZCkuCiovCmNvbnN0IGxsIElORiA9IDFlMTgrOTsKY29uc3QgbGwgTklORiA9IC0xZTE4LTk7CgoKI2RlZmluZSBkZWIoeCkgY2VyciA8PCAjeCA8PCIgIjsgX3ByaW50KHgpOyBjZXJyIDw8IGVuZGw7Cgp0ZW1wbGF0ZSA8Y2xhc3MgVD4gdm9pZCBfcHJpbnQoVCB4KXtjZXJyPDx4O30KdGVtcGxhdGUgPGNsYXNzIFQsIGNsYXNzIFY+IHZvaWQgX3ByaW50KHBhaXIgPFQsIFY+IHApIHtjZXJyIDw8ICJ7IjsgX3ByaW50KHAuRik7IGNlcnIgPDwgIiwiOyBfcHJpbnQocC5TKTsgY2VyciA8PCAifSI7fQp0ZW1wbGF0ZSA8Y2xhc3MgVD4gdm9pZCBfcHJpbnQodmVjdG9yIDxUPiB2KSB7Y2VyciA8PCAiWyAiOyBmb3IgKFQgaSA6IHYpIHtfcHJpbnQoaSk7IGNlcnIgPDwgIiAiO30gY2VyciA8PCAiXSI7fQp0ZW1wbGF0ZSA8Y2xhc3MgVD4gdm9pZCBfcHJpbnQoc2V0IDxUPiB2KSB7Y2VyciA8PCAiWyAiOyBmb3IgKFQgaSA6IHYpIHtfcHJpbnQoaSk7IGNlcnIgPDwgIiAiO30gY2VyciA8PCAiXSI7fQp0ZW1wbGF0ZSA8Y2xhc3MgVD4gdm9pZCBfcHJpbnQobXVsdGlzZXQgPFQ+IHYpIHtjZXJyIDw8ICJbICI7IGZvciAoVCBpIDogdikge19wcmludChpKTsgY2VyciA8PCAiICI7fSBjZXJyIDw8ICJdIjt9CnRlbXBsYXRlIDxjbGFzcyBULCBjbGFzcyBWPiB2b2lkIF9wcmludChtYXAgPFQsIFY+IHYpIHtjZXJyIDw8ICJbICI7IGZvciAoYXV0byBpIDogdikge19wcmludChpKTsgY2VyciA8PCAiICI7fSBjZXJyIDw8ICJdIjt9Cgp2aSBwcmltZXM7CnZpIHNwZjsKdmVjdG9yPGJvb2w+IHByaW1lOwoKLy8tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KbGwgZ2NkKGxsIGEsIGxsIGIpIHtpZiAoYiA+IGEpIHtyZXR1cm4gZ2NkKGIsIGEpO30gaWYgKGIgPT0gMCkge3JldHVybiBhO30gcmV0dXJuIGdjZChiLCBhICUgYik7fQpsbCBtcG93KGxsIGJhc2UsIGxsIGV4cCAsIGxsIG1vZCkgeyBiYXNlICU9IG1vZDsgbGwgcmVzdWx0ID0gMTsgd2hpbGUgKGV4cCA+IDApIHsgaWYgKGV4cCAmIDEpIHJlc3VsdCA9IChyZXN1bHQgKiBiYXNlKSAlIG1vZDsgYmFzZSA9IChiYXNlICogYmFzZSkgJSBtb2Q7IGV4cCA+Pj0gMTt9IHJldHVybiByZXN1bHQ7fQovL1VzZSB3aGVuICdhJyBhbmQgJ2InIGFyZSBsZXNzIHRoYW4gbW9kLGJ1dCB0aGVpciBhZGRpdGlvbiBjYW4gZ28gYmV5b25kIG1vZC4KbGwgbUFkZChsbCBhLCBsbCBiICwgbGwgbW9kKSB7cmV0dXJuIChhICsgYiA+PSBtb2QgPyBhICsgYiAtIG1vZCA6IGEgKyBiKTt9CnZvaWQgZXh0ZW5kZ2NkKGxsIGEsIGxsIGIsIGxsKnYpIHtpZiAoYiA9PSAwKSB7dlswXSA9IDE7IHZbMV0gPSAwOyB2WzJdID0gYTsgcmV0dXJuIDt9IGV4dGVuZGdjZChiLCBhICUgYiwgdik7IGxsIHggPSB2WzFdOyB2WzFdID0gdlswXSAtIHZbMV0gKiAoYSAvIGIpOyB2WzBdID0geDsgcmV0dXJuO30gLy9wYXNzIGFuIGFycnkgb2Ygc2l6ZTEgMwpsbCBtbWludihsbCBhLCBsbCBiKSB7bGwgYXJyWzNdOyBleHRlbmRnY2QoYSwgYiwgYXJyKTsgcmV0dXJuIGFyclswXTt9IC8vZm9yIG5vbiBwcmltZSBiCmxsIG1taW52cHJpbWUobGwgYSwgbGwgYikge3JldHVybiBtcG93KGEsIGIgLSAyLCBiKTt9CmJvb2wgcmV2c29ydChsbCBhLCBsbCBiKSB7cmV0dXJuIGEgPiBiO30Kdm9pZCBzd2FwKGxsICZ4LCBsbCAmeSkge2ludCB0ZW1wID0geDsgeCA9IHk7IHkgPSB0ZW1wO30KbGwgY29tYmluYXRpb24obGwgbiwgbGwgciwgbGwgbSwgbGwgKmZhY3QsIGxsICppZmFjdCkge2xsIHZhbDEgPSBmYWN0W25dOyBsbCB2YWwyID0gaWZhY3RbbiAtIHJdOyBsbCB2YWwzID0gaWZhY3Rbcl07IHJldHVybiAoKCh2YWwxICogdmFsMikgJSBtKSAqIHZhbDMpICUgbTt9CnZvaWQgZ29vZ2xlKGludCB0KSB7Y291dCA8PCAiQ2FzZSAjIiA8PCB0IDw8ICI6ICI7fQpsbCBtb2RfYWRkKGxsIGEsIGxsIGIsIGxsIG0pIHthID0gYSAlIG07IGIgPSBiICUgbTsgcmV0dXJuICgoKGEgKyBiKSAlIG0pICsgbSkgJSBtO30KbGwgbW9kX211bChsbCBhLCBsbCBiLCBsbCBtKSB7YSA9IGEgJSBtOyBiID0gYiAlIG07IHJldHVybiAoKChhICogYikgJSBtKSArIG0pICUgbTt9CmxsIG1vZF9zdWIobGwgYSwgbGwgYiwgbGwgbSkge2EgPSBhICUgbTsgYiA9IGIgJSBtOyByZXR1cm4gKCgoYSAtIGIpICUgbSkgKyBtKSAlIG07fQpsbCBtb2RfZGl2KGxsIGEsIGxsIGIsIGxsIG0pIHthID0gYSAlIG07IGIgPSBiICUgbTsgcmV0dXJuIChtb2RfbXVsKGEsIG1taW52cHJpbWUoYiwgbSksIG0pICsgbSkgJSBtO30gIC8vb25seSBmb3IgcHJpbWUgbQpsbCBwaGluKGxsIG4pIHtsbCBudW1iZXIgPSBuOyBpZiAobiAlIDIgPT0gMCkge251bWJlciAvPSAyOyB3aGlsZSAobiAlIDIgPT0gMCkgbiAvPSAyO30gZm9yIChsbCBpID0gMzsgaSA8PSBzcXJ0KG4pOyBpICs9IDIpIHtpZiAobiAlIGkgPT0gMCkge3doaWxlIChuICUgaSA9PSAwKW4gLz0gaTsgbnVtYmVyID0gKG51bWJlciAvIGkgKiAoaSAtIDEpKTt9fSBpZiAobiA+IDEpbnVtYmVyID0gKG51bWJlciAvIG4gKiAobiAtIDEpKSA7IHJldHVybiBudW1iZXI7fSAKdmVjdG9yPGxvbmcgbG9uZz4gY29tcHV0ZUhhc2goc3RyaW5nICZzKSB7bGwgc3RyX2xlbj1zLmxlbmd0aCgpOyBsbCBwX3Bvd1tzdHJfbGVuXTsgbGwgcD0xMjM7IHBfcG93WzBdPTE7IGZvcihpbnQgaT0xO2k8c3RyX2xlbjtpKyspIHBfcG93W2ldPShwX3Bvd1tpLTFdKnApJU1PRDM7IHZlY3Rvcjxsb25nIGxvbmc+IGhhc2goc3RyX2xlbisxKTsgaGFzaFswXT0wOyBmb3IoaW50IGk9MTtpPD1zdHJfbGVuO2krKykgaGFzaFtpXSA9ICggaGFzaFtpLTFdICsgKChzW2ktMV0tJ2EnKzEpKnBfcG93W2ktMV0pICVNT0QzICklTU9EMzsgcmV0dXJuIGhhc2g7IH0KdmVjdG9yPGludD4gbWFrZVphcnJheShzdHJpbmcgcykge2ludCBuID0gcy5sZW5ndGgoKTsgdmVjdG9yPGludD4geihuKTsgaW50IGw9MCxyPTA7IGZvcihpbnQgaT0xO2k8bjtpKyspIHtpZihpPD1yKSB6W2ldID0gbWluKHpbaS1sXSxyLWkrMSk7IHdoaWxlKGkreltpXTxuICYmIHNbeltpXV09PXNbaSt6W2ldXSkgeltpXSsrOyBpZihpK3pbaV0tMSA+IHIpIGw9aSAsIHI9aSt6W2ldLTE7IH0gcmV0dXJuIHo7IH0KLy9PKG5sb2dsb2duKQp2b2lkIHNpZXZlKGludCBuKSB7cHJpbWUuYXNzaWduKG4rMSx0cnVlKTsgcHJpbWVbMF09MDsgcHJpbWVbMV09MDsgZm9yIChpbnQgaSA9IDI7IGkgPD0gbjsgaSsrKWlmIChwcmltZVtpXSA9PSAxKSB7cHJpbWVzLmViKGkpOyBmb3IgKGxsIGogPSAobGwpaSAqIGk7IGogPD0gbjsgaiArPSBpKSB7aWYocHJpbWVbal0pIHByaW1lW2pdPTA7fSB9IH0KLy9PKG5sb2dsb2duKSBNYXggdmFsdWUgb2Ygbj0xZTYuCnZvaWQgZmluZF9zcGYoaW50IG4pIHtuID0gbWF4KG4sMSk7IHNwZi5hc3NpZ24obisxLDApOyBwcmltZS5hc3NpZ24obisxLHRydWUpOyBwcmltZVswXSA9IHByaW1lWzFdID0gZmFsc2U7IGludCBpOyBmb3IoaT0yOyBpPD1uOyBpKyspIHtpZihwcmltZVtpXSkge3ByaW1lcy5lYihpKTsgc3BmW2ldPWk7IGZvcihsbCBqPShsbClpKmk7IGo8PW47IGorPWkpIHtpZihwcmltZVtqXSkge3ByaW1lW2pdPWZhbHNlOyBzcGZbal09aTsgfSB9IH0gfSB9Ci8vTyhsb2cybikgdGltZSBhdCBtYXguIEJlZm9yZSBydW5uaW5nIHRoaXMgLCBSdW4gc2lldmUoaWYgbiBsYXJnZXIgdGhhbiAxZTYpIG9yIGZpbmRfc3BmKCkgaWYgbjw9MWU2LGJvdGggIHVwdG8gc3FydChuKS4KdnBsbCBwcmltZV9mYWN0b3JpemUobGwgbikgeyB2cGxsIHJlc3VsdDsgaWYobiA8IHNwZi5zaXplKCkpIHt3aGlsZShuIT0xKSB7bGwgZmFjdCA9IHNwZltuXTsgbGwgZXhwPTA7IGRvIHtuLz1mYWN0OyBleHArKzsgfSB3aGlsZShuJWZhY3Q9PTApOyByZXN1bHQuZWIoZmFjdCxleHApOyB9IHJldHVybiByZXN1bHQ7IH0gZWxzZSB7Zm9yKGF1dG8gcCA6IHByaW1lcykgeyBpZihwKnAgPiBuKSBicmVhazsgaWYobiAlIHA9PTApIHtyZXN1bHQuZW1wbGFjZV9iYWNrKHAsIDApOyBkbyB7biAvPSBwOyByZXN1bHQuYmFjaygpLnNlY29uZCsrOyB9IHdoaWxlIChuICUgcCA9PSAwKTsgfSB9IGlmKG4+MSkgcmVzdWx0LmViKG4sMSk7IHJldHVybiByZXN1bHQ7IH0gfQpsbCBzdW1wcmltZUV4cChsbCBuKSB7dnBsbCBwcmltZV9mYWN0b3JzID0gcHJpbWVfZmFjdG9yaXplKG4pOyBsbCBhbnM9MDsgZm9yKGF1dG8gcCA6IHByaW1lX2ZhY3RvcnMpIHthbnMrPXAuc2Vjb25kOyB9IHJldHVybiBhbnM7IH0KLy8tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KCmxsIG47CgpsbCBoZWxwZXJFdmVuKGxsIGssbGwgc3VtKXsKICAgIGlmKGs9PTApIHJldHVybiAxOwoKICAgIGxsIHZhbDEgPSAoc3VtKmhlbHBlckV2ZW4oay0xLHN1bSkpJU1PRDsKICAgIGxsIHZhbDIgPSBtcG93KDIsbiooay0xKSxNT0QpOwoKICAgIHJldHVybiAodmFsMSArIHZhbDIpJU1PRDsKfQoKbGwgaGVscGVyT2RkKGxsIGssbGwgc3VtKXsKICAgIGlmKGs9PTApIHJldHVybiAxOwoKICAgIGxsIHZhbDEgPSAoc3VtKmhlbHBlckV2ZW4oay0xLHN1bSkpJU1PRDsKCiAgICByZXR1cm4gdmFsMTsKfQoKaW50MzJfdCBtYWluKCkKewogICAgZmFzdF9pbzsKICAgIGludCB0OyAKICAgIGNpbj4+dDsKICAgIAogICAgbGwgTWF4ID0gMioxZTUgKyAxOwoKICAgIGxsIGZhY3RbTWF4XSxpZmFjdFtNYXhdOwogICAgZmFjdFswXT0xOyBpZmFjdFswXT0xOwoKICAgIGZvcihsbCBpPTE7aTw9TWF4LTE7aSsrKXsKICAgICAgICBmYWN0W2ldID0gKGZhY3RbaS0xXSppKSVNT0Q7CiAgICAgICAgaWZhY3RbaV0gPSBtbWludnByaW1lKGZhY3RbaV0sTU9EKTsKICAgIH0KCiAgICB3aGlsZSh0LS0pCiAgICB7CiAgICAgICAgbGwgazsgY2luPj5uPj5rOwoKICAgICAgICBsbCBzdW0gPSAwOwogICAgICAgIGlmKG4lMj09MCl7CiAgICAgICAgICAgIGZvcihsbCBpPTA7aTw9bi0yO2krPTIpewogICAgICAgICAgICAgICAgc3VtID0gKHN1bSArIGNvbWJpbmF0aW9uKG4saSxNT0QsZmFjdCxpZmFjdCkpJU1PRDsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgY291dDw8aGVscGVyRXZlbihrLHN1bSk7CiAgICAgICAgfSAgIAogICAgICAgIGVsc2V7CiAgICAgICAgICAgIGZvcihsbCBpPTA7aTw9bi0xO2krPTIpewogICAgICAgICAgICAgICAgc3VtID0gKHN1bSArIGNvbWJpbmF0aW9uKG4saSxNT0QsZmFjdCxpZmFjdCkpJU1PRDsgICAgCiAgICAgICAgICAgIH0gICAKICAgICAgICAgICAgY291dDw8aGVscGVyT2RkKGssKHN1bSsxKSVNT0QpOwogICAgICAgIH0gICAgICAgCiAgICAgICAgY291dDw8ZW5kbDsKICAgIH0KfQ==