CF2260G Sortable Permutations

A permutation of size $ n $ is an array of length $ n $ in which every integer from $ 1 $ to $ n $ appears exactly once. We call a permutation sortable if there exists an integer $ x\ge 2 $ such that the following property holds: if we remove from the permutation all elements at positions divisible by $ x $ , then the remaining array is strictly increasing. In other words, the elements at positions $ x,2x,3x,\ldots $ , not exceeding $ n $ , are removed, the order of the remaining elements is unchanged, and the resulting array must be strictly increasing. Positions are numbered starting from $ 1 $ . Count the number of sortable permutations of size $ n $ . Since the answer may be very large, output it modulo $ 998244353 $ .

The only line contains one integer $ n $ ( $ 1\le n\le 2\cdot10^5 $ ) — the size of the permutation.

Output one integer — the number of sortable permutations of size $ n $ , taken modulo $ 998244353 $ .

In the first example, the only permutation is $ [1] $ . For $ x=2 $ , nothing is removed, and the sequence is already sorted. In the second example, the sortable permutations are $ [1,2,3] $ , $ [1,3,2] $ , $ [2,1,3] $ , and $ [2,3,1] $ . For example, for the permutation $ [2,1,3] $ , $ x=2 $ works: after removing the second element, the sequence $ [2,3] $ remains. In the third example, one of the sortable permutations is $ [1,3,6,4,5,2] $ . For $ x=3 $ , the elements at positions $ 3 $ and $ 6 $ are removed, after which the strictly increasing sequence $ [1,3,4,5] $ remains.