Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Fibonacci Word Failure Function Sum

Limits: 2s, 512 MB

The following is based on true events:

One day Nabila decided that she wants to learn algorithms on String. She came to me for advice and I told her to start with KMP algorithm. I gave her some basic ideas on how KMP works and redirected her to “Introduction to Algorithm” book. There she learnt about KMP in more details.

While learning about KMP algorithm, she also learnt about “failure function”. What is the “failure function”? Basically, failure function is a table which is built for a particular string S, where for each substring s of form S[1…i], we store the length of the longest proper suffix (a proper suffix is a suffix which is not equal to the string itself) of s which is also a prefix of S at position i of failure function table.

For example, if we consider the following string: S = “accadaccac”, then it has the following failure function f(S):

S[i]accadaccac
f(S)[i]0001012342

Here above,
At i = 6 value of f(s)[6] = 1 because maximum prefix(‘a’) and suffix matching length is 1. At i = 9 value of f(s)[9] = 4 because maximum prefix(‘acca’) and suffix matching length is 4.

After learning the failure function, Nabila decided to practice calculating failure function on different strings.

The following is based on my imagination:

But eventually, Nabila became bored of calculating failure functions for common strings. So she decided to calculate failure functions for Fibonacci words. She defined the Fibonacci words as following:

F1 = a
F2 = b
F3 = ba
F4 = bab

Fn = Fn-1 + Fn-2

Here addition of Fibonacci words means concatenation of strings.

So Nabila picked a value for n, then calculated the value for Fn and then calculated the failure function for Fn. Here is what she did for n = 6, i.e, F6 = “babbabab”:

F6[i]babbabab
f(F6)[i]00112323

But eventually she got bored of this too! So in order to make the task more challenging, she tried to calculate the sum of the values in failure function table, SUM(f(Fn)).

For example, SUM(f(F6)) = SUM(f(“babbabab”)) = SUM([0,0,1,1,2,3,2,3]) = 0+0+1+1+2+3+2+3 = 12.

The task proved to be too hard for Nabila, so she brought it to me. I found it interesting, so I brought it to you :)

Given the value of n, please find the sum of the terms in failure function of Fn, where Fn is the nth fibonacci word. Since the answer can be large, print the answer modulo 1000000007.

Input

First line contains a single integer T ( 1 <= T <= 100000 ), number of test case. Next T lines contains a single integer in each line denoting n ( 1 <= n <= 1000000000 ).

Output

For each n in test case, output a single integer which is the sum of the terms in failure function of Fn, i.e, SUM(f(Fn)). Since the answer can be large, print the answer modulo 1000000007.

Samples

InputOutput
3
1
7
1000000000
0
36
2170

Author
  • forthright48's Avatar

    forthright48

    Samiul is a student at North South University and a part-time Software Engineer at Mukto Software Ltd. Sport programming is one of his hobbies. He loves reading manga - One Piece being his favorite.
Discussion
Submit

Login to submit