問題一覧 > 通常問題

No.1276 Three Cards

レベル : / AI推定難易度 : 2250 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 26
作問者 : PCTprobability / テスター : logx
お気に入りにしたユーザー ProblemId : 5194 / 自分の提出
問題文最終更新日: 2020-09-21 16:28:03
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 272 (Weird math contest) (順位表) の他の問題:

Problem Statement

You are given a positive integer $N$ that is at least $3$. PCT writes distinct integers between $1$ and $N$, inclusive, on $3$ cards $A,B,C$.

The integer written on $A$ was neither a divisor nor a multiple of the integer written on $B$, and the integer written on $B$ was a divisor of the integer written on $C$.

Find the number of possible combinations of the $3$ numbers written on the cards. Since the answer can be very large, output the remainder when it is divided by $1000000007$.

Input

$N$

  • All inputs are integers.
  • $3 \le N \le 2×10^9$

Output

Output the number of possible tuples of integers written on the cards, modulo $1000000007$. Print a newline at the end.

Sample

Sample 1
Input
4
Output
1

The only possible tuple of integers is $(3,2,4)$.

Sample 2
Input
150
Output
57731

Sample 3
Input
1000000000
Output
281351023

Output the remainder when divided by $1000000007$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。