{"problem":{"name":"Ex - Dice Product 2","description":{"content":"Snuke has a die (singular of dice) that shows integers from $1$ through $N$ with equal probability, and an integer $1$.   He repeats the following operation while his integer is less than or equal to ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc239_h"},"statements":[{"statement_type":"Markdown","content":"Snuke has a die (singular of dice) that shows integers from $1$ through $N$ with equal probability, and an integer $1$.  \nHe repeats the following operation while his integer is less than or equal to $M$.\n\n*   He rolls the die. If the die shows an integer $x$, he multiplies his integer by $x$.\n\nFind the expected value of the number of times he rolls the die until he stops, modulo $10^9+7$.\nDefinition of the expected value modulo $10^9+7$ We can prove that the desired expected value is always a rational number. Moreover, under the constraints of the problem, when the value is represented as an irreducible fraction $\\frac{P}{Q}$, we can also prove that $Q \\not\\equiv 0 \\pmod{10^9+7}$. Thus, an integer $R$ such that $R \\times Q \\equiv P \\pmod{10^9+7}$ and $0 \\leq R \\lt 10^9+7$ is uniquely determined. Answer such $R$.\n\n## Constraints\n\n*   $2 \\leq N \\leq 10^9$\n*   $1 \\leq M \\leq 10^9$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc239_h","tags":[],"sample_group":[["2 1","2\n\nThe answer is the expected value of the number of rolls until it shows $2$ for the first time. Thus, $2$ should be printed."],["2 39","12\n\nThe answer is the expected value of the number of rolls until it shows $2$ six times. Thus, $12$ should be printed."],["3 2","250000004\n\nThe answer is $\\frac{9}{4}$. We have $4 \\times 250000004 \\equiv 9 \\pmod{10^9+7}$, so $250000004$ should be printed.  \nNote that the answer should be printed modulo $\\bf{10^9 + 7 = 1000000007}$."],["2392 39239","984914531"],["1000000000 1000000000","776759630"]],"created_at":"2026-03-03 11:01:13"}}