{"problem":{"name":"G. LCM-er","description":{"content":"You are given four integers n, a, b and x. Your task is to count modulo 109 + 7 the number of sequences of integers A satisfying the following conditions: The only line of the input contains four int","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10113G"},"statements":[{"statement_type":"Markdown","content":"You are given four integers n, a, b and x. Your task is to count modulo 109 + 7 the number of sequences of integers A satisfying the following conditions:\n\nThe only line of the input contains four integers n, a, b and x (1 ≤ n ≤ 100, 1 ≤ a, b, x ≤ 109, a ≤ b).\n\nCount sequences of integers satisfying the given conditions. Print the answer modulo 109 + 7.\n\nIn the first sample there are 9 valid sequences: (1, 6), (2, 3), (2, 6), (3, 4), (3, 6), (4, 6), (5, 6), (6, 6), (6, 7).\n\n## Input\n\nThe only line of the input contains four integers n, a, b and x (1 ≤ n ≤ 100, 1 ≤ a, b, x ≤ 109, a ≤ b).\n\n## Output\n\nCount sequences of integers satisfying the given conditions. Print the answer modulo 109 + 7.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, a, b, x \\in \\mathbb{Z} $ be given integers with $ 1 \\leq n \\leq 100 $, $ 1 \\leq a \\leq b $, $ 1 \\leq x \\leq 10^9 $.  \nLet $ A = (A_1, A_2, \\dots, A_n) $ be a sequence of integers.\n\n**Constraints**  \n1. $ a \\leq A_i \\leq b $ for all $ i \\in \\{1, \\dots, n\\} $  \n2. $ \\gcd(A_1, A_2, \\dots, A_n) = x $\n\n**Objective**  \nCount the number of such sequences $ A $ modulo $ 10^9 + 7 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10113G","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}