配置

20组数据,传统型,没有SpecialJudge。

背景

当tangjz还很傻叉很傻叉的时候,萌萌哥哥送给tangjz一件礼物,tangjz看见里面有许多题,今天,他拿出了一道题与大家分享。

描述

求最小的正整数x使得g^{aX+b}\equiv c(mod\; p),无解输出"no solution"。保证p为质数。

输入格式

五个用空格隔开的正整数a, b, c, g, p,含义见描述。

输出格式

一个整数,表示X的值。

样例输入1

1 2 6 3 7

样例输出1

1

样例解释1

3^{1\ast 1+2}\equiv 27\equiv 6(mod\; 7)

样例输入2

1 2 6 4 7

样例输出2

no solution

样例解释2

4^{1}\equiv 4(mod\; 7)

4^{2}\equiv 2(mod\; 7)

4^{3}\equiv 1(mod\; 7)

4^{4}\equiv 4(mod\; 7)

...

样例输入输出3

比赛数据包\gift\gift.in和gift.out

数据范围与约定

  • 对于30%的数据:a,b,c,g\leq 10^{3}
  • 对于60%的数据:a,b,c,g,p\leq 10^{7}
  • 对于100%的数据:a,b,c,g\leq 10^{1,000,000},p< 2^{31}