b079. 直線排列與環狀排列

Content

有 $n$ 個數， $1$~$n$，

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

依順序排成一列，其方法數叫 $a_n$

例如 $n=4$ 時有

$1234$ $2134$ $1324$ $1243$ $2143$

共 $5$ 種排法

依順序排成一環，也就是 $1$ 跟 $n$ 也相鄰，其方法數叫 $b_n$

Input

$n$

$n ≤ 10^{15}$

Output

第一行輸出 $a_n$

第二行輸出 $b_n$

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

Sample Input #1

Sample Output #1

5
7

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (5%): 1.0s , <1K
公開測資點#1 (5%): 1.0s , <1K
公開測資點#2 (5%): 1.0s , <1K
公開測資點#3 (5%): 1.0s , <1K
公開測資點#4 (5%): 1.0s , <1K
公開測資點#5 (5%): 1.0s , <1K
公開測資點#6 (5%): 1.0s , <1K
公開測資點#7 (5%): 1.0s , <1K
公開測資點#8 (5%): 1.0s , <1K
公開測資點#9 (5%): 1.0s , <1K
公開測資點#10 (5%): 1.0s , <1K
公開測資點#11 (5%): 1.0s , <1K
公開測資點#12 (5%): 1.0s , <1K
公開測資點#13 (5%): 1.0s , <1K
公開測資點#14 (6%): 1.0s , <1K
公開測資點#15 (6%): 1.0s , <1K
公開測資點#16 (6%): 1.0s , <1K
公開測資點#17 (6%): 1.0s , <1K
公開測資點#18 (6%): 1.0s , <1K

Hint ：

Tags:

Binary Exponentiation matrix multiplication 快速冪

出處:

臺中一中電腦資訊研習社 [管理者：

Ching367436 (Ching367436)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」