Board game

3.2

10 votes
Math Basic, Algorithms, Basic Math, Math
Problem

You are playing a board game. The game consists of q cards. The ith card is a table with the following features:

  • 3 rows numbered from 1 to 3, considering the bottom to top approach
  • N columns numbered from 1 to n, considering the left to right approach 

In each move, you can move from a block with coordinates (x,y) to either of the following coordinates:

  • (x+1,y+1)
  • (x+1,y1)

You want to know the number of ways you can move from the block (1,1) to block (ni,3)

Note: Print the answer modulo 109+7.

Input format

  • First line: Integer q denoting the number of cards
  • Next q lines: ith card containing one integer nidenoting the size of the ith card

Output format

In q lines, print the answer that represents the number of ways you can move from the block (1,1) to block (ni,3).

Constraints

1q10001ni1018

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

There is only one way to go from (1,1) to (3,3) and that is [(1,1),(2,2),(3,3)].

There is no way to go from (1,1) to (2,3).

There are 2 ways to go from (1,1) to (5,3).

  • [(1,1),(2,2),(3,3),(4,2),(5,3)]
  • [(1,1),(2,2),(3,1),(4,2),(5,3)]
Editor Image

?