E - Sum of Sums of Restricted Sequences

マルチテストについての説明はこちら (サンプル問題を確認されていない方のみお読みください。)

配点： 点

個の正整数 があります．

ここで，以下の条件を満たすような長さ の整数列 すべてからなる集合 を考えます：

• ．

の値を求めてください．

• なお で数列 の各項の総和を表す．

ただし，答えは非常に大きくなる場合があるので， で割ったあまりを出力してください．

• 入力はすべて整数

各テストケースの入力は，それぞれ以下の形式で与えられる：

答えを求め， で割ったあまりを出力せよ．

1
2
2 3

21

ですから，答えは です．

2
5
1 4 1 4 2
9
9 9 8 2 4 4 3 5 3 

272
26127360