描述

    男主的女神这天给他发了消息,说如果他能做对她出的题就考虑和他交往。男主可高兴坏了,赶忙答应了,结果看到题目傻眼了。她的题目是:现有一数列{an},给出其前三项a1,a2,a3,以及要求的项的编号n,并且数列{an}只可能是等差数列或者是首项为1的等比数列,要求A输出第n项模100007后的值。由于运算量很大,男主找到了你来帮忙解决问题,请你你编写一个程序来帮助他。

输入格式

一行,四个整数,a1,a2,a3,n。

输出格式

一行,一个数,即an模100007的值。(负数取模答案为负)

样例输入

样例输入1:
1 2 3 5
样例输入2:
1 2 4 4

样例输出

样例输出1:
5
样例输出2:
8

数据范围与约定

对于30%的数据,保证0< |a1|,|a2|,|a3|≤102,0<n<102

对于50%的数据,保证0< |a1|,|a2|,|a3|≤104,0<n<104

对于70%的数据,保证0< |a1|,|a2|,|a3|≤106,0<n<106

对于100%的数据,保证0< |a1|,|a2|,|a3|≤109,0<n<109
 

来源

轩轩醉了