0967 - プレゼント交換

時間制限 2 秒 / メモリ制限 128 MB / 得点 50 / Writer a / x 1 / 統計 /

    タグ:
TLE
2sec
MLE
128MB
得点
50

ストーリー

ジングルベール♪ジングルベール♪鈴が鳴る～♪

今日は12月25日…そう,クリスマスなのである.
世間の人々は聖なる夜を楽しもうとウキウキしている中,今年もHM Technical Hiigh Schoolの情報処理部員(長いので以下HM処理部員)はいつもと変わらない平凡な1日を過ごそうとしていた.
しかし,そんな状況を見兼ねたHM処理部員の1人がこんな事を言いだした.

見兼ねたHM処理部員「今年のクリスマスはHM処理部の全員で集まってプレゼント交換をしよう!」

こうして今年のクリスマスはHM処理部員によるプレゼント交換会が行われる事となった.

問題

HM処理部員の人数はN人居て,あなたはその中の1人である.
N人のHM処理部員はそれぞれ各自で用意したプレゼントを1つずつ持っており,輪になって座っている.
席には0~N-1の番号が右回りで付けられている.
そしてQ枚の紙を用意してそれぞれに適当な自然数piを書いて束にする.

その後プレゼント交換は以下の行為を繰り返して行われる.

  1. Q枚の紙からランダムで1枚取り出す.
  2. プレゼントを右回り,左回りどちらの方向で回すかを決める.
  3. 取り出した紙に書かれた数だけHM処理部員がそれぞれ手に持っているプレゼントを隣の人に渡す.
  4. 取り出した紙は破棄し,Q枚の紙全てが無くなったら終了し,最後手元に残っているプレゼントを貰う.


あなたはa番の座席に座っており,b番の座席に座っている人が持ってきたプレゼントが欲しい.
b番の座席に座っている人が持ってきたプレゼントをあなたが手に入れるパターンが何通りあるか求めよ.

入力

    N Q
    
      p0
      .
      .
      pi
      .
      .
      pQ-1
    
      a b

1行目にHM処理部員の人数Nと用意した紙の枚数Qが空白区切りで与えられる.
2行目からQ+1行目にはそれぞれの紙に書かれた自然数piが与えられる.
Q+2行目にはあなたが座っている座席番号aと,あなたが欲しいプレゼントを持ってきた人が座っている座席番号bが空白区切りで与えられる.

出力

b番の座席に座っている人が持ってきたプレゼントをあなたが手に入れるパターンが何通りあるかを1行で出力せよ.
出力は大きくなる事があるので10007の剰余で表すこと.
また,出力の最後には改行を入れること.

制約

全ての入出力ケースについて以下を満たす。

  • 2 ≦ N ≦ 100
  • 1 ≦ Q ≦ 15
  • 1 ≦ pi ≦ 106
  • 0 ≦ a, b ≦ N-1

入出力例

入力例1

23 7
84
347
862
754787
45
865
47543778
8 19

出力例1

7346

入力例2

7 15
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
3 5

出力例2

5121

入力例3

2 15
1
1
1
1
1
1a
1
1
1
1
1
1
1
1
1
0 0

出力例3

0

解説

自分が欲しいものをプレゼント交換に持ってくるのは辞めよう.(戒め)




過去に作問したので良かったらHOJ453の「DB」も解いてください.