#include using namespace std; using ll = long long; constexpr ll mod = 998244353; template struct Mint { using M=Mint; ll v; M& put(ll x) { v=(x>=1; } return res; } M inv() { return pow(mod-2); } }; using mint = Mint; int main(){ cin.tie(0); cin.sync_with_stdio(0); ll n, a, b, c; cin >> n >> a >> b >> c; vector dp(n + 1, 1e18); dp[1] = 0; vector>> edges(n + 1); ll y = 1; ll y2 = 1; for(int x = 1; x < n; ++x){ edges[x].emplace_back((x + 1) % n, a); if(x == n - 1)edges[x].emplace_back(n + 1, a); ll xx2 = x; ll bb = b, xx = x; while(bb <= n * a){ bb *= b; xx = xx * x % n; xx2 = min(n, xx2 * x); if(xx2 == n)edges[x].emplace_back(xx2, bb); edges[x].emplace_back(xx, bb); } y2 = min(y2 * x, n); y = y * x % n; if(y2 == n)edges[x].emplace_back(y2, c); edges[x].emplace_back(y, c); } priority_queue, vector>, greater<>> que; que.emplace(0, 1); while(!que.empty()){ auto [cost, x] = que.top(); que.pop(); if(cost != dp[x])continue; for(auto [y, cost2] : edges[x]){ if(dp[y] > cost + cost2){ dp[y] = cost + cost2; que.emplace(dp[y], y); } } } dp[0] = min(dp[0], dp.back() + c); cout << dp[0] << endl; }