背景

tangjz又不在好好听课!老师把打瞌睡的tangjz叫起来回答问题,问题是这样的:

定义两个数列{an},{bn},并且满足a_1=p,a_{n+1}=a_n*p,b_1=q,b_{n+1}=q*a_n+r*b_n,其中n\in N^*,求b_n的表达式。

这个问题怎么会难倒tangjz…于是他回答完继续睡了…

描述

以上是几年前的tangjz…现在tangjz向你提出了一个问题:

已知n,q,r,p,求\sum_{i=1}^{n}b_i,这个问题对你来说也很简单吧!

为了方便计算,你只需要给出答案对2012182013取模的值即可。

输入格式

四个空格隔开的正整数n,q,r,p。

输出格式

一个整数,表示答案对2012182013取模的值。

样例输入

2 3 3 3

样例输出

21

样例解释

a_1=b_1=3,b_2=q*a_1+r*b_1=18,\sum_{i=1}^{2}b_i =21。

数据范围与约定

  • 对于30%的数据:n\le1000
  • 对于80%的数据:n\le2*10^9
  • 对于100%的数据:n\le10^{1,000,000},q,r,p<2*10^9
  • 数据均为随机生成,不含极限数据,请放心饮用。

来源

原创