Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #ifdef DEBUG
- #define _GLIBCXX_DEBUG
- #endif
- #include <bits/stdc++.h>
- using namespace std;
- typedef long double ld;
- #ifdef DEBUG
- #define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
- #else
- #define eprintf(...) ;
- #endif
- #define sz(x) ((int) (x).size())
- #define TASK "text"
- const int inf = (int) 1.01e9;
- const long long infll = (long long) 1.01e18;
- const ld eps = 1e-9;
- const ld pi = acos((ld) -1);
- #ifdef DEBUG
- mt19937 mrand(300);
- #else
- mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());
- #endif
- int rnd(int x) {
- return mrand() % x;
- }
- const int mod = (int) 1e9 + 7;
- int mul(int a, int b) {
- return (long long) a * b % mod;
- }
- void add(int &a, int b) {
- a += b;
- if (a >= mod) {
- a -= mod;
- }
- }
- int gcd(int a, int b) {
- return (b ? gcd(b, a % b) : a);
- }
- const int maxn = (int) 1e7 + 5;
- int lDiv[maxn], phi[maxn];
- vector<int> pr;
- int f[maxn], inv[maxn], finv[maxn];
- void precalc() {
- for (int i = 2; i < maxn; i++) {
- if (!lDiv[i]) {
- lDiv[i] = i;
- pr.push_back(i);
- }
- for (int j = 0; j < sz(pr) && pr[j] <= lDiv[i]; j++) {
- int p = pr[j] * i;
- if (p >= maxn) {
- break;
- }
- lDiv[p] = pr[j];
- }
- }
- phi[1] = 1;
- for (int i = 2; i < maxn; i++) {
- int p = lDiv[i];
- int j = i / p;
- if (lDiv[j] != p) {
- phi[i] = phi[j] * (p - 1);
- } else {
- phi[i] = phi[j] * p;
- }
- }
- f[0] = 1;
- for (int i = 1; i < maxn; i++) {
- f[i] = mul(f[i - 1], i);
- }
- inv[1] = 1;
- for (int i = 2; i < maxn; i++) {
- inv[i] = (mod - (long long) (mod / i) * inv[mod % i] % mod) % mod;
- }
- finv[0] = 1;
- for (int i = 1; i < maxn; i++) {
- finv[i] = mul(finv[i - 1], inv[i]);
- }
- }
- int c(int n, int k) {
- if (k < 0 || n < k) {
- return 0;
- }
- return mul(f[n], mul(finv[k], finv[n - k]));
- }
- int n, m;
- bool read() {
- if (scanf("%d%d", &m, &n) < 2) {
- return false;
- }
- return true;
- }
- int get(int d) {
- return mul(c(m / d - 1, n / d - 1), phi[d]);
- }
- void solve() {
- int res = 0;
- int g = gcd(n, m);
- for (int d = 1; d * d <= g; d++) {
- if (!(g % d)) {
- add(res, get(d));
- if (d * d != g) {
- add(res, get(g / d));
- }
- }
- }
- if (n & 1) {
- if (m & 1) {
- add(res, mul(c((m - 1) / 2, (n + 1) / 2 - 1), n));
- } else {
- add(res, mul(c(m / 2 - 1, (n + 1) / 2 - 1), n));
- }
- } else {
- if (!(m & 1)) {
- add(res, mul(c(m / 2 - 1, n / 2 - 1), n / 2));
- }
- for (int t0 = 0; t0 < 2; t0++) {
- for (int t1 = 0; t1 < 2; t1++) {
- int x = m;
- int nonzero = (n - 2) / 2;
- if (t0) {
- x--;
- } else {
- nonzero++;
- }
- if (t1) {
- x--;
- } else {
- nonzero++;
- }
- if (x & 1) {
- continue;
- }
- int y = (n - 2) / 2 + 2;
- add(res, mul(c(x / 2 - nonzero + y - 1, y - 1), n / 2));
- }
- }
- }
- res = mul(res, mul(inv[n], inv[2]));
- {
- int l = (m + 1) / 2;
- int bad = c(m - l, n - 1);
- if (n & 1) {
- int x = m - l;
- if (x & 1) {
- add(bad, c((x - 1) / 2, (n + 1) / 2 - 1));
- } else {
- add(bad, c(x / 2, (n + 1) / 2 - 1));
- }
- } else {
- for (int t0 = 0; t0 < 2; t0++) {
- for (int t1 = 0; t1 < 2; t1++) {
- int x = m - l;
- int nonzero = (n - 2) / 2;
- if (t0) {
- x--;
- }
- if (t1) {
- x--;
- } else {
- nonzero++;
- }
- if (x & 1) {
- continue;
- }
- int y = (n - 2) / 2 + 2;
- add(bad, c(x / 2 - nonzero + y - 1, y - 1));
- }
- }
- }
- bad = mul(bad, inv[2]);
- add(res, mod - bad);
- }
- printf("%d\n", res);
- }
- int main() {
- precalc();
- #ifdef DEBUG
- assert(freopen(TASK ".in", "r", stdin));
- assert(freopen(TASK ".out", "w", stdout));
- #endif
- int t;
- scanf("%d", &t);
- while (read()) {
- solve();
- #ifdef DEBUG
- eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
- #endif
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement