2863 - 愤怒的元首

   Pty生活在一个奇葩的国家，这个国家有n个城市，编号为1~n。
   每个城市到达其他城市的路径都是有向的。
   不存在两个城市可以互相到达。

这个国家的元首现在很愤怒，他大喊一声“气死偶咧！”，然后决定把所有的路径都毁掉再重建。 元首想知道有多少种重建的方案使得这个国家仍然奇葩。

Input

第一行一个整数：n

Output

   输出n个城市的重建方案数mod(10^9+7)的结果

Hint：基图不连通也是合法方案

Examples

Input

3

Output


                


                
                            

        


                    
Hint

            

                
：基图不连通也是合法方案
Sample Input
3
Sample Output
25
Hint
n <= 3000


            

        
            

            

        

            
            

                
                

                    Time Limit
                    
                        1 second                    
                

                

                    Memory Limit
                    128 MB
                

                
            

        


        

         Discuss                 Stats
        


         上一题
        下一题