#include "bits/stdc++.h" using namespace std; #define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i)) #define rep(i,j) FOR(i,0,j) #define each(x,y) for(auto &(x):(y)) #define mp make_pair #define mt make_tuple #define all(x) (x).begin(),(x).end() #define debug(x) cout<<#x<<": "<<(x)< pii; typedef vector vi; typedef vector vll; /*** c < 2p-1の場合不可 X = 0 c >= 2p-1の場合 X = p!H(p+1,c-2p+1) = p!C((p+1)+(c-2p+1)-1, c-2p+1) = p!C(c-p+1, c-2p+1) = p!C(c-p+1, c-p+1-(c-2p+1)) = p!C(c-p+1,p) = p!(c-p+1)!/(p!c-2p+1)! = (c-p+1)!/(c-2p+1)! Y = a!/b! mod md (a > b, mdは素数) floor(a/md) != floor(b/md)の場合すなわち a - b >= md の場合 Y ≡a!/b! ≡ a*...*(kmd)*...*b!/b! ≡ a*...*(kmd)*...*(b+1) ≡ a*...*0*...(b+1) ≡ 0 (c-p+1) - (c-2p+1) = p より p>=mdの場合 0 a-b= 0; --i) { if(s[i] == '9') { s[i] = '0'; if(i == 0) { s = '1' + s; break; } } else { s[i]++; break; } } return s; } string shiftRight(string s) { string t; int cur = 0, leading = 1; for(int i = 0; i < (int)s.size(); ++i) { cur = s[i] - '0' + cur * 10; int x = cur >> 1; if(!leading || x) { t += (char)(x + '0'); leading = 0; } cur &= 1; } if(t == "")t = "0"; return t; } bool les(string s, string t) { if(s.size() != t.size())return s.size() < t.size(); return s < t; } void generate() { vector res(MOD / R + 1); ll cur = 1; res[0] = 1; for(int i = 1; i < MOD; ++i) { cur = cur * i % MOD; if(i%R == 0) { res[i / R] = cur; } } each(r, res) { cout << r << ',' << endl; } } int digitsToMod(string s) { long long res = 0; for(auto c: s) { res = res * 10 + (c - '0'); if(res >= MOD)res %= MOD; } return (int)res; } int inverse(int x){ long long a = x, b = MOD, u = 1, v = 0; while(b) { long long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } if(u < 0)u += MOD; return (int)u; } int f(string C, string P) { string x = increment(C); x = shiftRight(x); if(C.back() == '1')x = increment(x); if(les(x, P) || les(to_string(MOD-1), P)) { return 0; } int c = digitsToMod(C); int p = digitsToMod(P); int a = (c - p + 1 + MOD) % MOD; int b = (c - 2 * p + 1 + MOD) % MOD; ll A = MAGIC[a / R], B = MAGIC[b / R]; for(int i = (int)a/R*R + 1; i <= a; ++i) A = A*i%MOD; for(int i = (int)b/R*R + 1; i <= b; ++i) B = B*i%MOD; int ans = A*inverse((int)B) % MOD; return ans; } int main(){ ios::sync_with_stdio(false); cin.tie(0); int T; cin >> T; while(T--) { string C, P; cin >> C >> P; cout << f(C, P) << endl; } }