有 \(n\) 個數， \(1\)\(None\)n~，

每個數可以選擇留於原處或是跟隔壁的交換，每個數最多可以換一次  

依順序排成一列，其方法數叫 \(a_n\)

例如 \(n=4\) 時有

\(1234\) \(2134\) \(1324\) \(1243\) \(2143\)

共 5 種排法   依順序排成一環，也就是 \(1\) 跟 \(n\) 也相鄰，其方法數叫 \(b_n\)

輸入格式

\(n\)

\(n ≤ 10^{15}\)

輸出格式

第一行輸出 \(a_n\)

第二行輸出 \(b_n\)

因為答案會很大，所以請輸出答案除以 \(10^9+7\) 的餘數

範例輸入

4

範例輸出

5
7