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

题目链接：

D. Iterated Linear Function

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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

7

input

3 4 2 1

output

25

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+;
const double PI=acos(-1.0);
const int inf=0x3f3f3f3f;
const int N=1e6+;
template<class T> void read(T&num) {
    char CH; bool F=false;
    for(CH=getchar();CH<''||CH>'';F= CH=='-',CH=getchar());
    for(num=;CH>=''&&CH<='';num=num*+CH-'',CH=getchar());
    F && (num=-num);
}
int stk[], tp;
template<class T> inline void print(T p) {
    if(!p) { puts(""); return; }
    while(p) stk[++ tp] = p%, p/=;
    while(tp) putchar(stk[tp--] + '');
    putchar('\n');
}

LL A,B,n,x;

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

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

    return ;
}