Cumulative Palindrome Count

All submissions for this problem are available.
Gru has been ordering the minions to do a lot of work lately. Minions don't want to trust Gru anymore. So, they propose a problem to Gru. They will only help Gru if he can answer the problem correctly. The minions generate an endless string $s$ by following these steps: 1. Let $s$ be an empty string. 2. $i = 1$. 3. Append $i$ *a* s to the back of $s$. 4. Append $i$ *b* s to the back of $s$. 5. Multiply $i$ by $2$ and go back to the third step. So $s$ will be *abaabbaaaabbbb...*. Now let's define $f(x)$ as number of distinct palindrome substring segments in $s[1 \ldots x]$. For example, $f(3) = 4$ because *a* (which is $s[1 \ldots 1]$), *b* (which is $s[2 \ldots 2]$), *a* (which is $s[3 \ldots 3]$) and *aba* (which is $s[1 \ldots 3]$) are possible palindrome substrings of $s[1 \ldots 3]$. The minions will give an integer $N$. Help Gru calculate ($\sum_{i=1}^{N} f(i)) \bmod{({10}^9 + 7)}$. Note: We are using 1indexing. ###Input:  First line will contain $T$, number of testcases. Then the testcases follow.  Each testcase contains a single line of input, which has one integer, $N$. ###Output: For each testcase, output in a single line, the answer modulo $({10}^9 + 7)$. ###Constraints  $1 \leq T \leq 10^3$  $1 \leq N \leq 10^{18}$ ###Sample Input: 1 3 ###Sample Output: 7 ###EXPLANATION: $f(1) = 1$, $f(2) = 2$, $f(3) = 4$. And so, the answer for $N = 3$ is $1+2+4 = 7$.Author:  mcdic 
Editorial  https://discuss.codechef.com/problems/CUPACO 
Tags  combinatorics, enigma, math, mcdic, plit2020 
Date Added:  18122019 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 