0, 1, 2 - Construction

2 secs 1024 MB
bayashiko

問題文


長さが であり、全ての要素が のいずれかであるような数列は全部で 個ありますが、そのうち以下の条件を満たすものの個数を で割った余りを求めてください。

  • 長さ の連続部分列であって、その総和が の倍数であるようなものが存在しない。

  

制約


  •   

入力


入力は以下の形式で標準入力から与えられます。

  

出力


答えを出力してください。

  

入力例1


3 3 6

出力例1


25

以外の計 個の数列が条件を満たします。  
 

入力例2


1 1 2

出力例2


1

のみが条件を満たします。 
 

入力例3


1000 8 10

出力例3


332011557

提出


Go (1.14)