#P1784. SoEasy!

SoEasy!

<v:shapetype id="_x0000_t75" stroked="f" filled="f" path="m@4@5l@4@11@9@11@9@5xe" o:preferrelative="t" o:spt="75" coordsize="21600,21600"><v:stroke joinstyle="miter"></v:stroke><v:formulas><v:f eqn="if lineDrawn pixelLineWidth 0"></v:f><v:f eqn="sum @0 1 0"></v:f><v:f eqn="sum 0 0 @1"></v:f><v:f eqn="prod @2 1 2"></v:f><v:f eqn="prod @3 21600 pixelWidth"></v:f><v:f eqn="prod @3 21600 pixelHeight"></v:f><v:f eqn="sum @0 0 1"></v:f><v:f eqn="prod @6 1 2"></v:f><v:f eqn="prod @7 21600 pixelWidth"></v:f><v:f eqn="sum @8 21600 0"></v:f><v:f eqn="prod @7 21600 pixelHeight"></v:f><v:f eqn="sum @10 21600 0"></v:f></v:formulas><v:path o:connecttype="rect" gradientshapeok="t" o:extrusionok="f"></v:path><o:lock aspectratio="t" v:ext="edit"></o:lock></v:shapetype><v:shape style="z-index:251657728;position:absolute;text-align:left;margin-top:170pt;width:118.75pt;height:136.55pt;margin-left:379.4pt;left:0px;mso-wrap-style:square;mso-position-horizontal-relative:page;mso-position-vertical-relative:page;" id="_x0000_s1026" type="#_x0000_t75"><v:imagedata o:title="" src="file:///C:\Users\GreyAnts\AppData\Local\Temp\msohtmlclip1\01\clip_image001.png"></v:imagedata><w:wrap type="square" anchory="page" anchorx="page"></w:wrap></v:shape>A sequence Sn is defined as:<o:p></o:p>

                     <o:p></o:p>

Where a, b, n, m are positive integers.┌x┐is the ceil of x. For example, ┌3.14┐=4. You are to calculate Sn.<o:p></o:p>

You, a top coder, say: So easy! <o:p></o:p>

Input

There are several test cases, each test case in one line contains four positive integers: a, b, n, m. Where 0< a, m < 2^15, (a-1)^2< b < a^2, 0 < b, n < 2^31.
The input will finish with the end of file.

Output

For each the case, output an integer Sn.

Sample Input

2 3 1 2013
2 3 2 2013
2 2 1 2013

Sample Output

</p>
4
14
4

HINT

Source