Advertisement
Guest User

Untitled

a guest
Oct 17th, 2019
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.67 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 a = 2, x = 1;
  14.     while(m>0) {
  15.         if(m&1) {
  16.             x*=a;
  17.             if(x>=1000000007) x%=1000000007;
  18.         }
  19.         a*=a;
  20.         if(a>=1000000007) a%=1000000007;
  21.         m>>=1;
  22.     }
  23.     x--;
  24.        
  25.     ll ans = 1;
  26.     while(n>0) {
  27.         if(n&1) {
  28.             ans*=x;
  29.             if(ans>=1000000007) ans%=1000000007;
  30.         }
  31.         x*=x;
  32.         if(x>=1000000007) x%=1000000007;
  33.         n>>=1;
  34.     }
  35.     cout << ans;
  36.    
  37.     return 0;
  38. }
  39. /*
  40. 6:6+15+20+15+6+1=63 (31+16*2)
  41. 5:5+10+10+5+1=31 (15+8*2)
  42. 4:4+6+4+1=15 (7+4*2)
  43. 3:3+3+1=7 (3+2*2)
  44. 2:2+1=3
  45. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement