Suppose you have n elements in the array 'a' numbered from 1 to n. It is...

Transcribed Image Text:

Suppose you have n elements in the array 'a' numbered from 1 to n. It is possible to remove the i-th element of 'a' if the number a[i] and i are relatively co-prime i.e. gcd (a[i],i)=1. After an element is removed, the elements to the right are shifted to the left by one position. An array b with n integers such that 1sb[i]sn-i+1 is a removal sequence for the array a if it is possible to remove all elements of a, if you remove the b1-th element, then the b2-th,..., then the bn-th element. For example, let a-[42,314]: [19,19] is a removal sequence: when you remove the 1-st element of the array, the condition gcd(42,19)=1 holds, and the array becomes [314];when you remove the 1-st element again, the condition gcd(314,19)=1 holds, and the array becomes empty. [2,1] is not a removal sequence: when you try to remove the 2-nd element, the condition gcd(314,2)=1 is false. An array is special if it has at least two removal sequences. For example, the array [1,2,5] is special: it has removal sequences [3,1,1] and [1,2,1]. The array [42,314] is not special: the only removal sequence it has is [1,1]. You are given two integers n and m. You have to calculate the number of special arrays a such that the length of a is from 1 to n and each ai is an integer from 1 to m. Input Format The first line of the input contains two integers n and m. Constraints Print one integer - the number of special arrays a such that the length of a is from 1 to n and each a[i] is an integer from 1 to m. Since the answer can be very large, print it modulo 998244353. Output Format 2sn3-10^5 1sm10^12 Sample Input 0 10 24 Sample Output 0 406957500 Sample Input 1 24 Sample Output 1 8 Suppose you have n elements in the array 'a' numbered from 1 to n. It is possible to remove the i-th element of 'a' if the number a[i] and i are relatively co-prime i.e. gcd (a[i],i)=1. After an element is removed, the elements to the right are shifted to the left by one position. An array b with n integers such that 1sb[i]sn-i+1 is a removal sequence for the array a if it is possible to remove all elements of a, if you remove the b1-th element, then the b2-th,..., then the bn-th element. For example, let a-[42,314]: [19,19] is a removal sequence: when you remove the 1-st element of the array, the condition gcd(42,19)=1 holds, and the array becomes [314];when you remove the 1-st element again, the condition gcd(314,19)=1 holds, and the array becomes empty. [2,1] is not a removal sequence: when you try to remove the 2-nd element, the condition gcd(314,2)=1 is false. An array is special if it has at least two removal sequences. For example, the array [1,2,5] is special: it has removal sequences [3,1,1] and [1,2,1]. The array [42,314] is not special: the only removal sequence it has is [1,1]. You are given two integers n and m. You have to calculate the number of special arrays a such that the length of a is from 1 to n and each ai is an integer from 1 to m. Input Format The first line of the input contains two integers n and m. Constraints Print one integer - the number of special arrays a such that the length of a is from 1 to n and each a[i] is an integer from 1 to m. Since the answer can be very large, print it modulo 998244353. Output Format 2sn3-10^5 1sm10^12 Sample Input 0 10 24 Sample Output 0 406957500 Sample Input 1 24 Sample Output 1 8