#include #include #include using namespace std; typedef long long ll; typedef unsigned int ul; typedef unsigned long long ull; typedef vector vi; typedef vector vc; typedef map mss; typedef map > mvii; typedef map mii; typedef queue qi; typedef map > mvis; typedef map > mvsi; typedef vector vs; typedef pair pii; #define MP make_pair #define all(c) c.begin(),c.end() #define present(container,element) (container.find(element)!=container.end()) // for set and map. #define cpresent(container,element) (find(all(container),element)!=container.end()) #define SORT(a) sort (a.begin(), a.end()) #define REVERSE(a) reverse (a.begin(), a.end()) #define PI acos(-1) #define ms(x,y) memset (x, y, sizeof(x)) #define INF 2000000000 #define pb push_back #define MAX 5000000 #define debug cout<<"A"<=b; i--) #define tr(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++) /* Direction Array */ // int fx[]={1,-1,0,0}; // int fy[]={0,0,1,-1}; // int fx[]={0,0,1,-1,-1,1,-1,1}; // int fy[]={-1,1,0,0,1,1,-1,-1}; template inline T bigmod(T p,T e,T M) { ll ret = 1; for(; e > 0; e >>= 1) { if(e & 1) ret = (ret * p) % M; p = (p * p) % M; } return (T)ret; } template inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);} template inline T modinverse(T a,T M){return bigmod(a,M-2,M);} template inline T lcm(T a,T b) {a=abs(a);b=abs(b); return (a/gcd(a,b))*b;} template inline bool getbit(T a, X i) { T t=1; return ((a&(t<0);} template inline T setbit(T a, X i) { T t=1;return (a|(t< inline T resetbit(T a, X i) { T t=1;return (a&(~(t<> a>> b>>t; //cout << pow(2,18); //cout << modInverse(pow(2,18),1000000007)<< endl; ll res1 = (bigmod((a+b)/2,t, 1000000007)) % 1000000007; //ll res2 = (bigmod(b/2,t, 1000000007)) % 1000000007; //ll res = (res1+res2)% 1000000007; cout << res1<< endl; return 0; }