# UVa 12045 - Fun with Strings

## Problem

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 1st 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 ith string is abab, (i+1)th string will be b(ab)b(ab) = babbab. He found that the Nth string has the length X and Mth string has the length Y. He wondered what will be length of the Kth 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 < 109 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.