codeforces 678D D. Iterated Linear Function(水题)

题目链接：

Consider a linear function f(x) = Ax + B. Let's define g(0)(x) = x and g(n)(x) = f(g(n - 1)(x)) for n > 0. For the given integer values A, B,n and x find the value of g(n)(x) modulo 109 + 7.

Input

The only line contains four integers A, B, n and x (1 ≤ A, B, x ≤ 109, 1 ≤ n ≤ 1018) — the parameters from the problem statement.

Note that the given value n can be too large, so you should use 64-bit integer type to store it. In C++ you can use the long longinteger type and in Java you can use long integer type.

Output

Print the only integer s — the value g(n)(x) modulo 109 + 7.

Examples

input

3 4 1 1

output

input

3 4 2 1

output

input

3 4 3 1

output

79

题意：

求这个式子的值;

思路：

最后是一个等比数列化简一下,注意一下A==1的情况;
ans=(A^n-1)/(A-1)*B+A^n*x;
A==1的时候ans=n*B+x;一个大水题;

AC代码：

//#include <bits/stdc++.h>

#include <iostream>
#include <queue>
#include <cmath>
#include <map>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
#define Riep(n) for(int i=1;i<=n;i++)
#define Riop(n) for(int i=0;i<n;i++)
#define Rjep(n) for(int j=1;j<=n;j++)
#define Rjop(n) for(int j=0;j<n;j++)
#define mst(ss,b) memset(ss,b,sizeof(ss));
typedef unsigned long long uLL;
typedef long long LL;
const LL mod=1e9+7;
const double PI=acos(-1.0);
const int inf=0x3f3f3f3f;
const int N=1e6+8;
template<class T> void read(T&num) {
    char CH; bool F=false;
    for(CH=getchar();CH<'0'||CH>'9';F= CH=='-',CH=getchar());
    for(num=0;CH>='0'&&CH<='9';num=num*10+CH-'0',CH=getchar());
    F && (num=-num);
}
int stk[70], tp;
template<class T> inline void print(T p) {
    if(!p) { puts("0"); return; }
    while(p) stk[++ tp] = p%10, p/=10;
    while(tp) putchar(stk[tp--] + '0');
    putchar('
');
}


LL A,B,n,x;

LL fastpow(LL fx,LL fy)
{
    LL s=1,base=fx;
    while(fy)
    {
        if(fy&1)s*=base,s%=mod;
        base*=base;
        base%=mod;
        fy=(fy>>1);
    }
    return s;
}

int main()
{
    read(A),read(B),read(n),read(x);
    LL temp1=fastpow(A-1,mod-2),temp2=fastpow(A,n);
    if(A==1)cout<<(n%mod*B+x)%mod<<"
";
    else cout<<(temp1*(temp2-1)%mod*B%mod+temp2*x%mod)%mod<<"
";

    return 0;
}