Hello @all,
Besides the presented solutions (the tester one and mine) there is a much more clever solution of which I was not aware of.
Sadly, my solution was too complicated, possibly because I wanted to make something look harder than what it actually was.
I thought that for a specific value of N (around 527.000) its binary representation would exceed the capacity of an unsigned long long and as such I used simple fast exponentiation below that “threshold” value and devised a simple grade-school arithmetic scheme to “get around” the “supposed” ULL overflow.
You can read it when the links are live 
The testers’ solution uses @mugurelionut scheme where the fact of not occuring any overflow just makes the task trivial with simple fast exponentiation (I really must have overlooked this fact while searching for C++ type limits).
Finally, the more theoretical solution which possibly lots of contestants used is based on a variation of Fermat’s Little Theorem that exploits the fact that:
2M-1 mod M = 1, where M = 109+7.
Therefore, we just output 2(2*N_bin % (M-1)) mod M
and we have correct answer!! As you can see, this trick would allow for a much higher constraint on the value of N assuming you would process it properly. Sadly, when I was told about this trick, I didn’t fully understood it (it was few months ago) and I ended up writing the most naive solution possible.
Hiroto Sekkido told me that even if M is changed, the sequence {20 mod M, 22 mod M, 22 mod M,…, 2k mod M, …} must be periodic (ignoring the first a few
terms), so such kind of cheat could be applicable.
I can leave here his solution using this approach as reference:
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define M 1000000007
#define ll long long
ll pw(ll a,ll b, ll md){
ll r;
if(!b) return 1;
r = pw(a,b/2,md);
r = (r*r)%md;
if(b%2) r = (r*a)%md;
return r;
}
int main(){
int T, N;
int B;
ll p, add;
scanf("%d",&T);
while(T--){
scanf("%d",&N);
B = 0;
p = 0; add = 1;
while(N){
if(N%2) p += add;
add = (add*10) % (M-1);
N /= 2;
}
p = (p*2)%(M-1);
printf("%d\n",(int)pw(2,p,M));
}
return 0;
}
This was the reason why the problem was set as EASY instead of MEDIUM.
Nontheless, I hope you have enjoyed it
Best,
Bruno
