{"problem":{"name":"G. Math, math everywhere","description":{"content":"_If you have gone that far, you'll probably skip unnecessary legends anyway..._ You are given a binary string and an integer . Find the number of integers _k_, 0 ≤ _k_ < _N_, such that for all _i_ = ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":5000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF765G"},"statements":[{"statement_type":"Markdown","content":"_If you have gone that far, you'll probably skip unnecessary legends anyway..._\n\nYou are given a binary string and an integer . Find the number of integers _k_, 0 ≤ _k_ < _N_, such that for all _i_ = 0, 1, ..., _m_ - 1\n\nPrint the answer modulo 109 + 7.\n\n## Input\n\nIn the first line of input there is a string _s_ consisting of 0's and 1's (1 ≤ |_s_| ≤ 40).\n\nIn the next line of input there is an integer _n_ (1 ≤ _n_ ≤ 5·105).\n\nEach of the next _n_ lines contains two space-separated integers _p__i_, α_i_ (1 ≤ _p__i_, α_i_ ≤ 109, _p__i_ is prime). All _p__i_ are distinct.\n\n## Output\n\nA single integer — the answer to the problem.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"_如果你已经走到这一步，你大概会直接跳过无用的背景故事……_\n\n给你一个二进制字符串 $s$ 和一个整数 $N$。求满足 $0 \\leq k < N$ 的整数 $k$ 的个数，使得对所有 $i = 0, 1, \\dots, m - 1$，都有\n\n输入的第一行是一个由 $0$ 和 $1$ 组成的字符串 $s$（$1 \\leq |s| \\leq 40$）。\n\n第二行是一个整数 $n$（$1 \\leq n \\leq 5 \\cdot 10^5$）。\n\n接下来的 $n$ 行，每行包含两个用空格分隔的整数 $p_i, \\alpha_i$（$1 \\leq p_i, \\alpha_i \\leq 10^9$，$p_i$ 是质数）。所有 $p_i$ 互不相同。\n\n输出一个整数 —— 本题的答案。\n\n## Input\n\n在第一行输入中，有一个由 $0$ 和 $1$ 组成的字符串 $s$（$1 \\leq |s| \\leq 40$）。在下一行输入中，有一个整数 $n$（$1 \\leq n \\leq 5 \\cdot 10^5$）。接下来的 $n$ 行，每行包含两个用空格分隔的整数 $p_i, \\alpha_i$（$1 \\leq p_i, \\alpha_i \\leq 10^9$，$p_i$ 是质数）。所有 $p_i$ 互不相同。\n\n## Output\n\n一个整数 —— 本题的答案。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Given a binary string $ s $ of length $ m $ ($ 1 \\leq m \\leq 40 $) and an integer $ n $ ($ 1 \\leq n \\leq 5 \\cdot 10^5 $), along with $ n $ distinct prime pairs $ (p_i, \\alpha_i) $ where $ 1 \\leq p_i, \\alpha_i \\leq 10^9 $, define:\n\nLet $ K = \\prod_{i=1}^n p_i^{\\alpha_i} $.\n\nFor each integer $ k \\in [0, K-1] $, let $ b_k $ be the binary string of length $ m $ formed by the least significant $ m $ bits of $ k $ (padded with leading zeros if necessary).\n\nCount the number of integers $ k \\in [0, K-1] $ such that $ b_k = s $.\n\n---\n\n**Formal Statement:**\n\nLet $ s \\in \\{0,1\\}^m $, $ K = \\prod_{i=1}^n p_i^{\\alpha_i} $.\n\nDefine the function $ f: \\mathbb{Z} \\to \\{0,1\\}^m $ by  \n$$\nf(k) = \\text{the } m\\text{-bit binary representation of } k \\bmod 2^m \\text{ (with leading zeros)}.\n$$\n\nCompute:\n$$\n\\left| \\left\\{ k \\in [0, K-1] \\mid f(k) = s \\right\\} \\right|\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF765G","tags":["brute force","dp","math","meet-in-the-middle","number theory"],"sample_group":[["1\n2\n2 1\n3 1","2"],["01\n2\n3 2\n5 1","15"],["1011\n1\n3 1000000000","411979884"]],"created_at":"2026-03-03 11:00:39"}}