F - You Got a Wrong Mail

小さな村のある郵便局に区別できる通の手紙があります。手紙には差出人と宛名が書いてありますが、すべての手紙についてどちらも雨に濡れて読めなくなってしまいました。しかし、どの手紙も村の人間から村の人間にあてられた手紙であることだけはわかります。
この村に住む人は相互にとても仲が良いので、あなたは手紙をランダムに届け、各人から正しい人に届けてもらうことにしました。

ところで村には人が住んでおり、実は番目の手紙は人に届くはずのものでした。
あなたが一人1枚ずつランダムに手紙を届けた時、1軒以上本来の届け先に正しく手紙を届けられるような届け方は何通りありますか?(このような届け方の例は入力例1を参考にしてください)

答えは非常に大きくなる可能性があるのでで割ったあまりを求めてください。

入力は以下の形式で与えられる

条件を満たすような手紙の配り方の総数をで割ったあまりを答えよ

4

15

例えばから順にというような届け方をすると4軒目には正しく配送できています。
1, 2, 3軒目は間違っていますが、1件以上届け先が正しいのでこのような届け方も答えに含みます。

124816

732757679

で割ることを忘れないでください。