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 length X and M^th string has length Y. He wondered what will be length of the K^th string. Can you help him?

Input starts with an integer T (≤ 200), denoting the number of test cases.

Each case begins with five integers N, X, M, Y, K. (0 < N, M, X, Y, K < 10⁹ and N ≠ M).

For each case print one line containing the case number and L which is the desired length modulo 1000000007 (10⁹ + 7) or the string Impossible if it's not possible.