PALACE - Accomodate the palace

no tags 

There is a big palace in which rooms are constructed in the from of a square matrix. Now these rooms have to be filled with people.

As there are conflicts between people to maintain the equilibrium total number of people must be odd in every row and every column.

A room can accommodate only a single person.

Given the size of palace N one has to find total number of ways people can be accommodated.

Input

First line consists of an integer K and then K test cases follow.

Output

For each test case you have to output the result%98777 in a separate line.

Example

Input:
1
3

Output:
16

hide comments
urimaj: 2020-04-01 21:07:41

Hint : Use last row and last column to adjust the parity

ravi_joe: 2018-08-31 11:38:09

how to approach this problem ?

Ajey Golsangi: 2011-08-05 17:02:55

What do you mean by "total number of ways people can be accomodatede in that" ?

:(){ :|: & };:: 2010-07-29 20:22:33


And who will give range of N and K ?

যোবায়ের: 2010-04-22 22:42:23

int is sufficient

Iqram Mahmud: 2010-04-12 14:32:13

What's the limit of N ?


Added by:Abhilash I
Date:2006-12-30
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:IIIT Hyderabad Local Programming Contest