CF1750D Count GCD

You are given two integers $ n $ and $ m $ and an array $ a $ of $ n $ integers. For each $ 1 \le i \le n $ it holds that $ 1 \le a_i \le m $ . Your task is to count the number of different arrays $ b $ of length $ n $ such that: - $ 1 \le b_i \le m $ for each $ 1 \le i \le n $ , and - $ \gcd(b_1,b_2,b_3,...,b_i) = a_i $ for each $ 1 \le i \le n $ . Here $ \gcd(a_1,a_2,\dots,a_i) $ denotes the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers $ a_1,a_2,\ldots,a_i $ . Since this number can be too large, print it modulo $ 998\,244\,353 $ .

N/A

N/A

In the first test case, the possible arrays $ b $ are: - $ [4,2,1] $ ; - $ [4,2,3] $ ; - $ [4,2,5] $ . In the second test case, the only array satisfying the demands is $ [1,1] $ . In the third test case, it can be proven no such array exists.