りあんさんは文字列 "A" を 個、文字列 "B" を 個、文字列 "AB" を 個持っています。
これらを全て連結して長さ の文字列を作るとき、作られる文字列としてありうるものが何通りあるかを求めてください。
ただし、この値は非常に大きくなる可能性があるので、 で割ったあまりを出力してください。
この問題では一つの入力につきテストケースが 個与えられます。
入力は以下の形式で与えられます。
:
行出力してください。
行目には ケース目 の答えを出力してください。
5 1 1 1 1 3 1 10 0 10 1000 1000 0 1000 1000 1000
5 14 184756 72475738 314702404