{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"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\u003csup\u003est\u003c/sup\u003e string and generated subsequent strings from it by replacing all the **b**\u0027s with **ab** and all the **a**\u0027s with **b**. For example, if he **i\u003csup\u003eth\u003c/sup\u003e** string is **abab**, **(i+1)\u003csup\u003eth\u003c/sup\u003e** string will be **b(ab)b(ab) \u003d babbab**. He found that the **N\u003csup\u003eth\u003c/sup\u003e** string has length **X** and **M**\u003csup\u003eth\u003c/sup\u003e string has length **Y**. He wondered what will be length of the **K\u003csup\u003eth\u003c/sup\u003e** string. Can you help him?"}},{"title":"Input","value":{"format":"MD","content":"Input starts with an integer **T (\u0026le; 200)**, denoting the number of test cases.\n\nEach case begins with five integers **N, X, M, Y, K. (0 \u0026lt; N, M, X, Y, K \u0026lt; 10\u003csup\u003e9\u003c/sup\u003e and N \u0026ne; M)**."}},{"title":"Output","value":{"format":"MD","content":"For each case print one line containing the case number and **L** which is the desired length modulo **1000000007 (10\u003csup\u003e9\u003c/sup\u003e + 7)** or the string `Impossible` if it\u0027s not possible."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n3 16 5 42 6\n5 1 6 10 9\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 68\nCase 2: Impossible\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}