C# Truly O(N) solution, 4 lines
f(n) = f(n-1) * m(n) + n\n\nm(1)=2\nm(2)=4\nm(3)=4\nm(4)=8\n....\nm(n) increases only when (n & n - 1) == 0\n\n\npublic class Solution\n{\n    public int Concat
f(n) = f(n-1) * m(n) + n\n\nm(1)=2\nm(2)=4\nm(3)=4\nm(4)=8\n....\nm(n) increases only when (n & n - 1) == 0\n\n```\npublic class Solution\n{\n    public int ConcatenatedBinary(int n)\n    {\n        long m = 1, res = 0, mod = (long)Math.Pow(10, 9) + 7;\n        for (int i = 1; i <= n; i++)\n        {\n            if (i == m) // or ((i & i - 1) == 0)\n                m <<= 1;\n            res = (res * m + i) % mod;\n        }\n        return (int)res;\n    }\n}\n```\n\n\nShorter version\n```\npublic class Solution\n{\n    public int ConcatenatedBinary(int n)\n    {\n        long m = 1, res = 0, mod = (long)Math.Pow(10, 9) + 7;\n        for (int i = 1; i <= n; i++)\n            res = (res * (i == m ? m <<= 1 : m) + i) % mod;\n        return (int)res;\n    }\n}\n```
[]