#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;
template<typename T>
struct DP3x
{
int N1, N2, N3;
vector<T> data;
DP3x(int, int N2, int N3, const T& t = T())
: N1(2), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()*sizeof(T) < (1<<26)); }
T& operator()(int i1, int i2, int i3)
{ i1&=1; return data[ ((i1*N2)+i2)*N3+i3 ]; }
void swap(DP3x& rhs)
{ data.swap(rhs.data); }
};
static const LL inf = (1LL << 60);
class RoadOrFlightHard { public:
long long minTime(int N, int roadFirst, int roadProd, int roadAdd, int roadMod, int flightFirst, int flightProd, int flightAdd, int flightMod, int K)
{
// input
vector<LL> rt(N), ft(N);
{
rt[0] = roadFirst % roadMod;
for(int i=1; i<N; ++i)
rt[i] = (LL(rt[i-1])*roadProd + roadAdd) % roadMod;
}
{
ft[0] = flightFirst % flightMod;
for(int i=1; i<N; ++i)
ft[i] = (LL(ft[i-1])*flightProd + flightAdd) % flightMod;
}
DP3x<LL> dp(N+1, K+1, 2);
for(int n=0; n<=N; ++n)
for(int k=0; k<=K; ++k)
if( n == 0 ) {
dp(n,k,0) = 0;
dp(n,k,1) = inf;
}
else {
dp(n,k,0) = min(dp(n-1,k,0), dp(n-1,k,1)) + rt[n-1];
if( k == 0 )
dp(n,k,1) = inf;
else
dp(n,k,1) = min(dp(n-1,k,1), dp(n-1,k-1,0)) + ft[n-1];
}
LL ans = inf;
for(int k=0; k<=K; ++k)
ans = min(ans, min(dp(N,k,0), dp(N,k,1)));
return ans;
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
{ ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const long long& Expected, const long long& Received) {
bool ok = (Expected == Received);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, RoadOrFlightHard().minTime(N, roadFirst, roadProd, roadAdd, roadMod, flightFirst, flightProd, flightAdd, flightMod, K));}
int main(){
CASE(0)
int N = 3;
int roadFirst = 14;
int roadProd = 1;
int roadAdd = 2;
int roadMod = 10;
int flightFirst = 18;
int flightProd = 1;
int flightAdd = 10;
int flightMod = 17;
int K = 1;
long long _ = 14LL;
END
CASE(1)
int N = 3;
int roadFirst = 4;
int roadProd = 1;
int roadAdd = 2;
int roadMod = 10;
int flightFirst = 1;
int flightProd = 1;
int flightAdd = 10;
int flightMod = 17;
int K = 2;
long long _ = 11LL;
END
CASE(2)
int N = 3;
int roadFirst = 4;
int roadProd = 1;
int roadAdd = 2;
int roadMod = 10;
int flightFirst = 1;
int flightProd = 1;
int flightAdd = 6;
int flightMod = 9;
int K = 1;
long long _ = 12LL;
END
CASE(3)
int N = 5;
int roadFirst = 85739;
int roadProd = 94847;
int roadAdd = 93893;
int roadMod = 98392;
int flightFirst = 92840;
int flightProd = 93802;
int flightAdd = 93830;
int flightMod = 92790;
int K = 3;
long long _ = 122365LL;
END
CASE(4)
int N = 1;
int roadFirst = 2;
int roadProd = 1;
int roadAdd = 1;
int roadMod = 100;
int flightFirst = 1;
int flightProd = 1;
int flightAdd = 1;
int flightMod = 2;
int K = 0;
long long _ = 2LL;
END
CASE(4)
int N = 1;
int roadFirst = 2;
int roadProd = 1;
int roadAdd = 1;
int roadMod = 100;
int flightFirst = 1;
int flightProd = 1;
int flightAdd = 1;
int flightMod = 2;
int K = 1;
long long _ = 1LL;
END
CASE(5)
int N = 1;
int roadFirst = 0;
int roadProd = 1;
int roadAdd = 1;
int roadMod = 100;
int flightFirst = 0;
int flightProd = 1;
int flightAdd = 1;
int flightMod = 1;
int K = 1;
long long _ = 0LL;
END
CASE(6)
int N = 400000;
int roadFirst = 1234;
int roadProd = 56789;
int roadAdd = 32323;
int roadMod = 99999;
int flightFirst = 9876;
int flightProd = 44344;
int flightAdd = 7865;
int flightMod = 99999;
int K = 40;
long long _ = -1LL;
END
}
// END CUT HERE