問題文

正整数r,dr,dが与えられます. また,あなたは変数xxを持っており,それは11で初期化されています.

あなたは以下の操作を好きな順序で00回以上何度でも行うことができます.

  • xx×rx \leftarrow x \times rと更新する
  • xx+dx \leftarrow x + dと更新する

ここで正整数yyが与えられます.何回か操作を行いxxyyにできるか判定してください. また,xxyyにすることができる場合は操作を行う最小回数を答えてください.

制約

  • 1r,d1051 \leq r,d \leq 10^5
  • 1y1051 \leq y \leq 10^5
  • 入力される値はすべて整数である

入力

入力は以下の形式で標準入力から与えられます.

rrdd
yy

出力

何回か操作を行いxxyyにできる場合は11行目にYesと出力し,22行目に操作回数の最小値を出力せよ. どのように操作を行ってもxxyyにできない場合はNo11行に出力せよ.

サンプル

入力1
2 3
10
出力1
Yes
3

以下のように操作するのが最適です.

  • 11つ目の操作を行いx1×2x \leftarrow 1 \times 2と更新する
  • 22つ目の操作を行いx2+3x \leftarrow 2 + 3と更新する
  • 11つ目の操作を行いx5×2x \leftarrow 5 \times 2と更新する

よって33回の操作でxx1010にすることができました. また,これより少ない操作回数で条件を満たすことはできないのでこのような出力が正解となります.

入力2
2 3
12
出力2
No

どのように操作を行ってもxx1212にすることはできません. よってこのような出力が正解となります.

提出


Go (1.21)