B"Let us call an edge-weighted tree with n vertices numbered from 1 to n good if the weight of each edge is either 1 or -1 and for each vertex i , the product of the edge weights of all edges having i as one endpoint is -1 . You are given a positive integer n . There are n^{n-2} cdot 2^{n-1} distinct ^ dagger edge-weighted trees with n vertices numbered from 1 to n such that each edge is either 1 or -1 . Your task is to find the sum of d(1,n)^ ddagger of all such trees that are good. Since the answer can be quite large, you only need to find it modulo 998 ,244 ,353 . ^ dagger Two trees are considered to be distinct if either: Note that by Cayley's formula, the number of trees on n labeled vertices is n^{n-2} . Since we have n-1 edges, there are 2^{n-1} possible assignment of weights(weight can either be 1 or -1 ). That is why total number of distinct edge-weighted tree is n^{n-2} cdot 2^{n-1} . ^ ddagger d(u,v) denotes the sum of the weight of all edges on the unique simple path from u to v . The first and only line of input contains a single integer n ( 1 <= q n <= q 5 cdot 10^5 ). The only line of output should contain a single integer, the required answer, modulo 998 ,244 ,353 . In the first test case, there is only 1 distinct good tree. The value of d(1,2) for that tree is -1 , which is 998 ,244 ,352 under modulo 998 ,244 ,353 . In the second test case, the value of d(1,1) for any tree is 0 , so the answer is 0 . In the third test case, there are 16 distinct good trees. The value of d(1,4) is: The sum of d(1,4) over all trees is 2 cdot (-2) + 8 cdot (-1) + 4 cdot (0) + 2 cdot (1) = -10 , which is 998 ,244 ,343 under modulo 998 ,244 ,353 . "...