問題一覧 > 通常問題

No.1277 級数入り級数

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 10
作問者 : 神鳥奈紗神鳥奈紗 / テスター : 57tggx57tggx
1 ProblemId : 5402 / 出題時の順位表
問題文最終更新日: 2020-10-30 22:24:14

問題文

神鳥さんはPCT君から次のような問題を出されました。

$S_n=\displaystyle\sum_{\displaystyle a_1,\ldots,a_n>0} \frac1{\displaystyle\prod_{k=1}^n a_k\left(\left(\sum_{k=1}^n a_k\right)-1 \right)}$

とおきます。すると、

$\displaystyle S_n=\sum_{i=1}^m b_i\zeta(c_i)$

を満たす長さ $m$ の整数列 $b,c$ と正整数 $m$ が存在します。

このような $b,c,m$ のうち、$m$ が最小となるような $b,c,m$ を求めてください。
しかし、神鳥さんはこの問題を解けません。あなたは神鳥さんの代わりにこの問題を解いてください。

ただし、この級数は指定された範囲内で収束することが保証されています。

入力

$n$

  • 入力は全て整数である。
  • $1 < n \le 10^{7}$
  • 出力

    1行目に $m$ の値を出力してください。

    2行目に $b$ の要素を全て掛け合わせたものを $10^9+7$ で割った余りを出力してください。

    3行目に $c$ の要素を全て掛け合わせたものを $10^9+7$ で割った余りを出力してください。

    これらの値は一意に定まることが保証されています。

    また、ここでの整数 $x$ を $10^9+7$ で割った余りとは、 $x ≡ p (mod 10^9+7)$ を満たす最小の非負整数 $p$ のことです。

    最後に改行してください。

    サンプル

    サンプル1
    入力
    2
    出力
    1
    2
    2

    $\displaystyle\sum_{a_1,a_2>0} \frac1{a_1a_2(a_1+a_2-1)}=2\zeta(2)$ です。

    この場合、 $m=1$ 、 $b$ の要素の積は $2$ 、 $c$ の要素の積は $2$ であるため、このように出力してください。

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