Time-3 - I'm Not Blind!

AC報酬: ラテコイン

⌛

今年も、夏祭りの季節がやってきました。
Targetrate君はその祭りに行きました。祭りには懐かしの屋台があったり、屋台の食べ物が売られていました。今日も活気がある祭りです。

その中でも一番目玉なのは「射的」です。Targetrate君は屋台の食べ物を食べたそ～に見つめながらそのゲームに参加しました。
しかしこのゲームはかなり難易度が高いという噂を聞きました。その理由は、射撃の的が動くのです。止まってる的でさえあんな難しいのに、なぜ回転させたのでしょうかね...
何はともあれ、ではさっそくやってみましょう！！

...結果は、Targetrate君だけが知っています。Targetrate君の友達であるmatcharate君も、流石に得点は知りたいと思っています。
そう思ってるうち、Targetrate君は独り言をつぶやきました。

「いや～... 枚の的だけ外しちゃった。。。もう一回やる！！！」

全く。負けず嫌いですねこの人は。
と、思っているとTargetrate君はこう言ってきました。

「じゃあ、今から言う情報だけで自分が何点とったか当ててみて！！そしたら報酬あげるわ！！」

なぜ報酬をくれるんでしょうか...？

枚の的があります。それぞれの的には と番号づけられています。最初、的 には数値 が書かれています。

その後、 秒後にすべての的がランダムな位置に移動します。このとき同じ位置に つ以上の的が来ることはありません。
具体的には 番目の的の位置 として、数列 は 以上 以下の整数からなる順列 に等しいか、それを並び替えたものに等しくなります。

matcharate君はTargetrate君の得点を知りたいと思っています。
Targetrate君の独り言によると、左から 番目の的を撃ち落とすことができなかったようです。それ以外は全て撃ち落とすことができたようです。

Targetrate君の得点は撃ち落とせた的に書かれた数字の合計となります。
すなわち を並び替えたもの に対して、得点は となります。ただし において に対し です。

-Mission-
十分な時間この射的で遊んだ時、Targetrate君が得た可能性がある得点は何通りあるか。報告せよ。

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

• はすべて異なる
• 入力はすべて整数

答えを出力せよ。

3 1
1 2 3
1

3

順列 を並び替えた数列 とすると 番目だけ撃ち落とせなかったので となります。
よって考えられるのは次の 通りです。

• 番目のこの順で的があったとき、得点は です。
• 番目のこの順で的があったとき、得点は です。
• 番目のこの順で的があったとき、得点は です。

3 1
1 1 1
1

1

どのように的が動いたとしても、考えられる得点は のみです。

3 0
1 2 3

1

全ての的を撃ち落としました。matcharate君は射撃の天才なのかもしれません。

7 3
6 1 9 3 7 1 8
2 4 5

18