Tom 在公司专门负责信件的处理，他每天的工作是将信装到信封里，然后投递出去。一天，Jone来看Tom 他无意中将信封的顺序调乱了，Tom装完信后才发现，所有的信都不在它应该在的信封里，他觉得太巧了，他想知道对于N封信，到底有多少种可能让所有的信都不在它应在的信封里。
输入：
一个正整数N（表示有N封信要处理）
输出：
一个整数（表示让所有信都不在它应在的信封里的方案总数，由于结里可能较大，我们要求输出结果对32768的余数）
样例：输入：
4
输出：
9
对于60%的数据N<=1000;
对于100%的数据N<=100000;