{"trustable":false,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cscript type\u003d\u0027text/x-mathjax-config\u0027\u003eMathJax.Hub.Config({tex2jax: { inlineMath: [[\u0027$\u0027,\u0027$\u0027]] } }); \u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027 src\u003d\u0027https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\u0027\u003e\u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027\u003esetTimeout(function(){MathJax.Hub.Queue([\u0027Typeset\u0027, MathJax.Hub, \u0027left_view\u0027]);}, 2000);\u003c/script\u003e\n\u003cdiv class\u003d\"panel_content\"\u003e\n \u003cp\u003e潘会长给协会捐了一颗星球---潘星,并且在上面留了好多好多道题目,但是他不想让你们很轻易的得到,因此把题目分散在潘星赤道上面(潘星是一颗巨大的星球,赤道有无限远)。\u003c/p\u003e\n\u003cp\u003e潘会长遨游宇宙之前告诉了你每道题目的编号都等于前两个放置地点题目的乘积(a[n]\u003da[n-1]*a[n-2]),并告诉了你0号放置点与1号放置点的题目编号,但是粗心的潘会长忘记将每个题目的位置留给了你。\n现在,你想知道编号为n的题目放在哪个放置点上。(数据量可能太大了,请将结果对1e9+7进行取余)\n\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"输入包含多组测试数据;\n\u003cbr\u003e每组数据占一行,包含3个整数a, b, n( 0 \u0026lt;\u003d a, b, n \u0026lt;\u003d 10^9 ),分别为0号放置点与1号放置点的题目编号,以及你想要知道位置的题目的编号。"}},{"title":"Output","value":{"format":"HTML","content":"对每组测试数据请输出一个整数,由于结果可能很大,你只需输出对1000000007取模后的结果即可,每组数据输出一行。"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e0 1 0\n6 10 2\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e0\n60\u003c/pre\u003e"}}]}