## 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 accomodate only a single person.
Given the size of palace N one has to find total number of ways people can be accomodatede in that.

### Input

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

### Output

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

### Example

```Input:
1
3
Output:
16
```

hide comments
 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