#include <bits/stdc++.h>
using namespace std;
#define sc(a) scanf("%d", &a)
#define sc2(a, b) scanf("%d%d", &a, &b)
#define sc3(a, b, c) scanf("%d%d%d", &a, &b, &c)
#define scs(a) scanf("%s", a)
#define pri(x) printf("%d\n", x)
#define prie(x) printf("%d ", x)
#define mp make_pair
#define pb push_back
#define BUFF ios::sync_with_stdio(false);
#define db(x) cerr << #x << " == " << x << endl
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef vector<ll> vi;
typedef vector<vector<ll> > vvi;
typedef vector<ii> vii;
typedef vector< vii> vvii;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;
const ld pi = acos(-1);
int MOD = 1;
int n=2;
vvi matmul(vvi &m1, vvi &m2)
{
  vvi ans;
  ans.resize(m1.size(), vi(m2.size(), 0));
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      for (int k = 0; k < n; k++) {
        ans[i][j] += m1[i][k] * m2[k][j];
        ans[i][j] %= MOD;
      }
  return ans;
}
vvi matpow(vvi &m1, ll p)
{
  vvi ans;
  ans.resize(m1.size(), vi(m1.size(), 0));
  for (int i = 0; i < n; i++) ans[i][i] = 1;
  while (p) {
    if (p & 1) ans = matmul(ans, m1);
    m1 = matmul(m1, m1);
    p >>= 1;
  }
  return ans;
}
// VETOR TEM N LINHAS E A MATRIZ E QUADRADA
vi mulvet(vvi &m1, vi &vet)
{
  vi ans;
  ans.resize(vet.size(), 0);
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) {
      ans[i] += (m1[i][j] * vet[j]);
      ans[i] %= MOD;
    }
  return ans;
}
int main()
{
	ll a,b,n,k;
  cin>>a>>b>>n>>k;
  for(int i=0;i<k;i++) MOD*=10;
  vvi m1(2, vi(2, 0));
  m1[0][0] = a;
  m1[0][1] = b;
  m1[1][0] = 1;
  m1[1][1] = a;

  vvi m2(2, vi(2, 0));
  m2[0][0] = a;
  m2[0][1] = -b;
  m2[1][0] = -1;
  m2[1][1] = a;
  m1= matpow(m1, n-1);
  m2= matpow(m2, n-1);
  vi v(2, 0);
  vi v2(2, 0);
  v[0] = v2[0] = a;
  v[1] = 1;
  v2[1] = -1;

  vi cu= mulvet(m1, v);
  vi cu2= mulvet(m2, v2);

  ll resp= cu[0] + cu2[0];

  resp%=MOD;
  resp+=MOD;
  resp%=MOD;
  if(n%2==0 or a*a>=b){
    if(a*a == b) resp++;
    resp--;
  }
  resp= (resp+MOD)%MOD;
  resp%=MOD;
  MOD/=10;
  cout<<resp/MOD<<endl;
  return 0;
}