輸入格式

給定 \(g\) ,\(p\) ,\(A\) ,\(B\)     \(g,p≤2^{30}\), \(A, B ≤ p\)

輸出格式

\(K\)

範例輸入

3 233 169 96

範例輸出

157

提示

部分測資 \(g,b,a,p≤99999\)