{"trustable":true,"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":"\u003cdiv class\u003d\"panel_content\"\u003eWithout expecting, Angel replied quickly.She says: \"I\u0027v heard that you\u0027r a very clever boy. So if you wanna me be your GF, you should solve the problem called GF~. \"\u003cbr\u003eHow good an opportunity that Gardon can not give up! The \"Problem GF\" told by Angel is actually \"Gauss Fibonacci\".\u003cbr\u003eAs we know ,Gauss is the famous mathematician who worked out the sum from 1 to 100 very quickly, and Fibonacci is the crazy man who invented some numbers.\u003cbr\u003e\u003cbr\u003eArithmetic progression:\u003cbr\u003eg(i)\u003dk*i+b;\u003cbr\u003eWe assume k and b are both non-nagetive integers.\u003cbr\u003e\u003cbr\u003eFibonacci Numbers:\u003cbr\u003ef(0)\u003d0\u003cbr\u003ef(1)\u003d1\u003cbr\u003ef(n)\u003df(n-1)+f(n-2) (n\u0026gt;\u003d2)\u003cbr\u003e\u003cbr\u003eThe Gauss Fibonacci problem is described as follows:\u003cbr\u003eGiven k,b,n ,calculate the sum of every f(g(i)) for 0\u0026lt;\u003di\u0026lt;n\u003cbr\u003eThe answer may be very large, so you should divide this answer by M and just output the remainder instead.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The input contains serveral lines. For each line there are four non-nagetive integers: k,b,n,M\u003cbr\u003eEach of them will not exceed 1,000,000,000.\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each line input, out the value described above."}},{"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 1 4 100\r\n2 0 4 100\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e21\r\n12\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}