問題一覧 > 通常問題

No.1276 3枚のカード

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 20
作問者 : PCTprobabilityPCTprobability / テスター : logxlogx
3 ProblemId : 5194 / 出題時の順位表
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。