#include #include using namespace std; using namespace atcoder; const long mod=1000000007; long f(long a,long b,long N){ for(int i=0;i>A>>B>>C>>D>>N; assert(A<=B); assert(C<=D); assert(abs(A)<=1e9); assert(abs(B)<=1e9); assert(abs(C)<=1e9); assert(abs(D)<=1e9); assert(0<=N); assert(N<=1e18); ans=max({f(A,C,N%8),f(A,D,N%8),f(B,C,N%8),f(B,D,N%8)})%mod*pow_mod(16,N/8,mod)%mod; if(ans<0){ cout<