class Solution {
int mod = 1000000007;
public int concatenatedBinary(int n) {
long ans = 0;
for (int i = 1; i <= n; i++) {
ans = (ans << getLength(i)) + i;
ans %= mod;
}
return (int) ans;
}
int getLength(int n) {
for (int i = 31; i >= 0; i--) {
int ans = n >> i & 1;
if (ans == 1) return i + 1;
}
return 0;
}
}