{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"Let\u0027s define another number sequence, given by the following function:\n\n$$\nf(n) \u003d\n\\begin{cases}\na, \u0026 \\text{if $n$ \u003d 0} \\\\\\\\\nb, \u0026 \\text{if $n$ \u003d 1} \\\\\\\\\nf(n - 1) + f(n - 2), \u0026 \\text{if $n$ \u003e 1}\n\\end{cases}\n$$\n\nWhen **a \u003d 0** and **b \u003d 1**, this sequence gives the Fibonacci sequence. Changing the values of **a** and **b**, you will be able to get many different sequences.\n\nGiven the values of **a, b**, you have to find the least **m** significant digits of **f(n)**."}},{"title":"Input","value":{"format":"MD","content":"Input starts with an integer **T (\u0026#8804; 10000)**, denoting the number of test cases.\n\nEach test case consists of a single line containing four integers **a b n m**. The values of **a** and **b** range in **[0,100]**, value of **n** ranges in **[0, 10\u003csup\u003e9\u003c/sup\u003e]** and value of **m** ranges in **[1, 4]**."}},{"title":"Output","value":{"format":"MD","content":"For each case, print the case number and the last **m** digits of **f(n)**. However, do **NOT** print any leading zero."}},{"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\u003e4\n0 1 11 3\n0 1 42 4\n0 1 22 4\n0 1 21 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 89\nCase 2: 4296\nCase 3: 7711\nCase 4: 946\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}