#include #include #include #include #include #include using namespace __gnu_pbds; using namespace std; using namespace atcoder; using mint = modint; constexpr int MAX_N = 10000000; bitset is_composite;//prime_divisor[i]はiを割り切る素数の1つ vector primes = {2}; int main(){ int M, N; scanf("%d\n%d", &M, &N); if(M < N){ printf("00000000\n"); return 0; }else if(M == N){ printf("00000001\n"); return 0; } for (int i = 4; i <= MAX_N; i += 2){ is_composite.set(i); } int _i = 3; for (int twoi; _i*_i <= MAX_N; _i += 2){ if(!is_composite[_i]){ primes.push_back(_i); twoi = _i<<1; for (int j = _i*_i; j <= MAX_N; j += twoi){ is_composite.set(j); } } } for (; _i <= MAX_N; _i += 2) if(!is_composite[_i]) primes.push_back(_i); gp_hash_table prime_factorization;//注目している数を素因数分解したときの<素因数, 割り切る回数> auto solve = [&](int x, bool add){ for(auto &i : primes){ if(x < i) break; int cnt = 0, _x = x; while((_x /= i)){ cnt += _x; } prime_factorization[i] += add ? cnt : -cnt; } }; solve(M, true); solve(N, false); solve(M-N, false); mint::set_mod(100000000); mint answer{1}; for(auto [num, pow] : prime_factorization) if(pow) answer *= mint::raw(num).pow(pow); printf("%08u\n", answer.val()); return 0; }