{"raw_statement":[{"iden":"statement","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."},{"iden":"input","content":"In 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."},{"iden":"output","content":"A single integer — the answer to the problem."},{"iden":"examples","content":"Input\n\n1\n2\n2 1\n3 1\n\nOutput\n\n2\n\nInput\n\n01\n2\n3 2\n5 1\n\nOutput\n\n15\n\nInput\n\n1011\n1\n3 1000000000\n\nOutput\n\n411979884"}],"translated_statement":[{"iden":"statement","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输出一个整数 —— 本题的答案。"},{"iden":"input","content":"在第一行输入中，有一个由 $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$ 互不相同。"},{"iden":"output","content":"一个整数 —— 本题的答案。"},{"iden":"examples","content":"输入122 13 1输出2输入0123 25 1输出15输入101113 1000000000输出411979884"}],"sample_group":[],"show_order":[],"formal_statement":"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$$","simple_statement":null,"has_page_source":false}