CERI2018E - A recurrence relation


Our task is to print some terms of the sequence defined by :

  • $u_0 = 0$ ;
  • $u_1 = 1$ ;
  • for $n\geqslant 0$, $u_{n+2} = 5u_{n+1}^2 - 3u_n$.

    Input

    The first line of the input consist of a single integer number t which determines the number of tests.

    In each of next t lines there is a single integer number n.

    Constraints

    • 0 < t ≤ 30 000
    • 0 < n < 1 000 000

    Output

    Print un modulo 1 000 000 007

    Example

    Input:
    3
    2
    3
    10
    Output:
    5
    122
    360914800
    

  • hide comments
    [Rampage] Blue.Mary: 2018-05-04 06:53:05

    There are two typos in problem description:
    (1) "for n > 1 ..." should be "for n >= 0 ..."
    (2) The last line of Example Input should be "10" instead of "100".

    =(Francky)=> Many thanks

    Last edit: 2018-05-04 11:04:44

    Added by:Francky
    Date:2018-05-03
    Time limit:5s-10s
    Source limit:50000B
    Memory limit:1536MB
    Cluster: Cube (Intel G860)
    Languages:All