#include #include #include using namespace std; typedef long long lint; typedef vectorvi; typedef pairpii; #define rep(i,n)for(int i=0;i<(int)(n);++i) const lint mod=1e9+7; lint powmod(lint x,lint e){ lint prod=1%mod; for(int i=63;i>=0;--i){ prod=prod*prod%mod; if(e&1LL<>b>>c>>d; b%=mod; c%=mod; lint x=b*c%mod; x=x*powmod((c-1+mod)%mod,mod-2)%mod; lint y=(mod-x)%mod; lint u=powmod(c,d); u=u*x%mod; u=(u+y)%mod; if(c==1){ u=(d%mod)*b%mod; } cout<