No.1276 3枚のカード
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 24
作問者 :
PCTprobability
/ テスター :
logx
タグ : / 解いたユーザー数 24
作問者 :
PCTprobability
/ テスター :
logx
問題文最終更新日: 2020-09-21 16:28:03
問題文
$3$ 以上の正整数 $N$ が与えられます。 ここで PCT 君は $3$ 枚のカード $A,B,C$ に相異なる $1$ 以上 $N$ 以下の整数を書き込みます。
この時 $A$ に書かれた整数は $B$ に書かれた整数の約数でも倍数でもなく、 $B$ に書かれた整数は $C$ に書かれた整数の約数でした。
カードに書かれた $3$ 個の数字としてあり得るものは何通りあるか求めてください。 ただし答えは非常に大きくなることがあるので $1000000007$ で割った余りを出力してください。
入力
$N$
- 入力は全て整数である。
- $3 \le N \le 2×10^9$
出力
カードに書かれた整数の組としてあり得るものが何通りあるかを $1000000007$ で割った余りを出力してください。最後に改行してください。
サンプル
サンプル1
入力
4
出力
1
あり得る整数の組としては $(3,2,4)$ のみが考えられます。
サンプル2
入力
150
出力
57731
サンプル3
入力
1000000000
出力
281351023
$1000000007$ で割った余りを出力してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。