Scanf.scanf "%d" (fun t ->
    let calc n =
        let co = [|
            [| 869418286; 727008098; 660103155; 183023413; 471090892; 417297686; 237315285; 542573865;
               444014759; 927321758; 184117322; 5655049;   347662323; 346175634; 765144583; 0         |];
            [| 869418286; 727008098; 660103155; 183023413; 471090892; 417297686; 237315285; 542573865;
               444014759; 927321758; 184117322; 962779130; 404391958; 700407153; 729548371; 539588932 |]
        |].(n mod 2)
        in
        Array.fold_left (fun acc v -> (acc * n + v) mod 1000000007) 0 co |> Printf.printf "%d\n"
    in
    for i = 1 to t do
        Scanf.scanf " %d" calc
    done
)