1472 - 最长上升子序列

现在有一个长度为n的随机排列，求它的最长上升子序列长度的期望。
为了避免精度误差，你只需要输出答案模998244353的余数。

Input 


输入只包含一个正整数n。


对于 100%的数据，1≤n≤28。<br />

共有 25组数据  ，对于第 i组数据 （1≤i≤25）， n=i+3。 

<br />


Output


<div>
	输出只包含一个非负整数，表示答案模998244353的余数。
</div>
<div>
	可以证明，答案一定为有理数，设其为a/b（a、b为互质的整数），你输出的整数为x，
</div>
<div>
	则你需要保证0≤x&lt;998244353且a与bx模998244353同余。
</div>
<div>
</div>


Sample Input


<span class="sampledata">2</span> 


Sample Output


<span class="sampledata">499122178<br />

【样例说明】
这是3/2。

输入

输出

样例

输入


                

                

                    
输出

                    

                


                
                            

        


        
                    
来源

            

                
BJWC2018 高级


            

            

            

        

            
            

                
                

                    时间限制
                    
                        1 秒                    
                

                

                    内存限制
                    512 MB
                

                
            

        


        

         讨论                 统计
        


         上一题
        下一题