#include using namespace std; typedef long long ll; typedef vector vi; typedef vector vl; typedef pair pii; typedef pair pll; typedef int _loop_int; #define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i) #define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i) #define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i) #define DEBUG(x) cout<<#x<<": "<>n>>m; // gcd(a[0], a[1]) = m // after operation, // b[0] = gcd(a[0], a[1]) = a[0] / s // b[1] = lcm(a[1], a[2]) = a[1] * t // and next operation, // b2[0] = gcd(b[0], b[1]) = gcd(a[0]/s, a[1]*t) = a[0]/s = gcd(a[0], a[1]) // a[0] = x * m // a[1] = y * m // x \perp y // 1 <= x*m < y*m <= n // answer = count (x,y) * 2 * (n-2)! mod M ll sum = 0; for(int y=2;y*m<=n;y++){ ll tmp = y; ll add = y; for(int x=2;x*x<=tmp;x++){ if(tmp%x==0){ while(tmp%x==0)tmp/=x; add /= x; add *= (x-1); } } if(tmp>1){ add /= tmp; add *= (tmp-1); } sum += add; sum %= MOD; } sum = sum * 2 % MOD; FOR(i,1,n-1){ sum = sum * i % MOD; } printf("%lld\n",sum); return 0; }