Advertisement
Guest User

Untitled

a guest
Oct 17th, 2019
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.57 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. #define endl '\n'
  6.  
  7. int main() {
  8.     ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
  9.    
  10.     ll n, m;
  11.     cin >> n >> m;
  12.    
  13.     ll x = 1, a = 2;;
  14.     for(int i = 1; i < m; i++) {
  15.         x+=a;
  16.         if(x>=1000000007) x%=1000000007;
  17.         a*=2;
  18.     }
  19.        
  20.     ll ans = 1;
  21.     while(n>0) {
  22.         if(n&1) {
  23.             ans*=x;
  24.             x*=x;
  25.             if(x>=1000000007) x%=1000000007;
  26.         }
  27.         n>>=1;
  28.     }
  29.     cout << ans;
  30.    
  31.     return 0;
  32. }
  33. /*
  34. 6:6+15+20+15+6+1=63 (31+16*2)
  35. 5:5+10+10+5+1=31 (15+8*2)
  36. 4:4+6+4+1=15 (7+4*2)
  37. 3:3+3+1=7 (3+2*2)
  38. 2:2+1=3
  39. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement