Problem F - Fun with Strings

Zibon just started his courses in Computer science. After having some lectures on programming courses he fell in love with strings. He started to play with strings and experiments on them. One day he started a string of arbitrary (of course positive) length consisting of only {a, b}. He considered it as 1^st string and generated subsequent strings from it by replacing all the b's with ab and all the a's with b. For example, if he i^th string is abab, (i+1)^th string will be b(ab)b(ab) = babbab. He found that the N^th string has the length X and M^th string has the length Y. He wondered what will be length of the K^th string. Can you help him?

Input

The first line of the input file contains an integer T (T ≤ 1000) which denotes the total number of test cases. The description of each test case is given below:

Five integers N, X, M, Y and K where (0 < N, M, X, Y, K < 10⁹ and N ≠ M).

Output

For each test case produce one line of output giving either the number which is desired length (modulo 1000000007) or the string "Impossible". You output Impossible if the given input is not possible.

2
3 16 5 42 6
5 1 6 10 9

68
Impossible