title: Finding sum of all binary expansions of numbers from 1 to n
body: <p>Recently, I came across a question posted as a challenge at a competitive site. There it was asked to find the sum of all the decimal interpretation of binary representations of numbers from 1 to n. Suppose when n = 4, so, sum will be 1 + 10 + 11 + 100 = 122. Since this number could be very large so answer should be modulo 1000000007.
  I came across the following solutions but was not able to optimize it.</p>
  <pre><code>#include&lt;iostream&gt;
  #include&lt;queue&gt;
  using namespace std;
  int Mod(string s, int a)
  {
      int res = 0, i, l = s.size();
      for( i = 0 ; i &lt; l ; i++ )
      {
          res = ( res * 10 + s[i] - '0' ) % a;
      }
      return res;
  }
  int main()
  {
      int t;
      cin &gt;&gt; t;
      while(t--)
      {
          long long n;
          cin &gt;&gt; n;
          int Sum = 0, mod = 1000000007;
          queue&lt;string&gt; q;
          q.push(&quot;1&quot;);
          while( n &gt; 0 )
          {
              n--;
              string s1 = q.front();
              q.pop();
              Sum = ( Sum + Mod(s1, mod) ) % mod;
              string s2 = s1;
              q.push(s1.append(&quot;0&quot;));
              q.push(s2.append(&quot;1&quot;));
          }
          cout &lt;&lt; Sum &lt;&lt; endl;
      }
      return 0;
  }
  </code></pre>
  <p>Constraints:
  1 &lt;= t &lt;= 10^5, 1 &lt;= n &lt;= 10^18, Allowed Time = 1 sec. Any optimization help would be admirable. Thanks in advance.</p>