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

Valentine’s day is coming. (I know, it’s still 9 months away, but bear with me) Najib is planning a surprise gift for his wife. Among other gifts and surprises, he will give a bouquet of flowers to her. Since it is a special gift, certain specifications have to met in making the bouquet.

The bouquet will contain * N* flowers of 4 types. The types of flowers and their specifications are as follows:

- The number of roses must be even.
- The number of tulips must be a multiple of 5.
- There can be at most 4 lilies.
- There can be at most 1 hydrangeas.

Last valentine’s day, Najib forgot to wish his wife. He doesn’t want to mess up this time. This is why he is starting so early. Now help him by counting the number of ways he can make the bouquet.

The first line will contain a single integer * T (1 ≤ T ≤ 10^{5})* denoting the number of test cases.

The following

For each test case, output a single integer denoting the answer modulo * 10^{18}*. Print a newline after each output.

Input | Output |
---|---|

1 6 | 7 |

**Note:**

There are 7 ways to form a bouquet with 6 flowers:

93% Solution Ratio

saifkhan007420Earliest,

Fazlerabbi.Fastest, 0.0s

dip_BRURLightest, 1.4 MB

mdvirusShortest, 63B

Login to submit