COMPLEX2 - HELP ABHISHEK(version-II)

no tags 

ABHISHEK is weak of mathematics he is not able to solve the sequences frequently. So he invited topcoders to develop a program for solving the sequence. He managed to solve the other kind of sequences except one kind.

The sequence description is as follows:

    (x-w)(x-w^2)(x-w^3)(x-w^4) ... (x-w^(n-1))

where x is a number and w is nth root of unity.

Input

first line contain number of test cases t. Then t line follow x and n. x and n separated by a space.

Constraints:

2 <= x <= 1000

2 <= n <= 1000

t <= 410

Output

Print the result per test case according to above sequence and also keep in mind if there is any term in decimal then write it in form of a fraction. see the I/O for further detail.

Example

Input:
1
5 10

Output:
9765624/4

Time limit is strict, so optimise your solution as you can. First try the tutorial version at COMPLEX1


hide comments
vishu: 2015-08-23 01:53:22

My first program in python \(^_^)/

RIVU DAS: 2015-06-29 17:38:11

Nice question!

Pranet Verma: 2013-06-06 23:20:51

will the numerator portion fit in 64 bits?

No

Last edit: 2013-06-12 13:46:40
Anshu Avinash: 2012-06-23 05:43:12

Increase time limit to atleast 1s!I am stuck at 0.91s.
Finally AC :)

Last edit: 2012-06-23 06:29:18
Abhishek Mishra: 2012-06-19 15:09:05

@jhanvi have you solved the sequence first.
if not then solve it u will reached to formula.
see my below comments..

jaans: 2012-06-19 05:11:16

for which case we have to print num/den and for which whole number :O can't understand!!!plss help!

Abhishek Mishra: 2012-06-18 17:48:17

@alex i saw ur solution you have use basic input/output by the way u r ryt we generally have to focus on questions rather than fast I/O.
yeah in some languages it's hard to submit the answer in case of c++ even the simpler cin/cout will do ur wrk..

Last edit: 2012-06-17 19:39:44
Alex Anderson: 2012-06-18 17:48:17

I give up. I don't care about fast I/O, just solving the problem and I've done that. My I/O is fast enough, just not for this.

Abhishek Mishra: 2012-06-18 17:48:17

use fast i/o

Alex Anderson: 2012-06-18 17:48:17

Optimize my solution? I just can't calculate the answer fast enough. Maybe I should solve MUL first, but it probably wouldn't help.

Last edit: 2012-06-17 07:45:46

Added by:Abhishek Mishra
Date:2012-06-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:My own