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 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,X,M,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. Sample Input 2 3 16 5 42 6 5 1 6 10 9 Sample Output 68 Impossible