D. Василий баавгай ба гоё тэмдэгт мөр

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Василий баавгай гоё тэмдэгт мөрд үнэхээр дуртай. Хэрвээ дараах шалгууруудыг хангаж байвал $s$ нь гоё тэмдэгт мөр:

  1. $s$ тэмдэгт мөр нь зөвхөн $0$ ба $1$ тэмдэгтүүдийг агуулна. $s$ тэмдэгт мөр яг $n$ ширхэг $0$, $m$ ширхэг $1$-н тэмдэгт агуулсан байх ёстой.
  2. Бид $s$ тэмдэгт мөрөөс өөрчлөлтiiн ямар нэг (магадгүй, тэг) тоо $g$ тэмдэгт авч болно. $g$ тэмдэгт нь тэг эсвэл нэг байна.

Хамгийн багадаа хоёр урттай тэмдэгт мөрийн өөрчлөлт дараах үйлдэл: бид тэмдэгт мөрөөс сүүлийн хоёр тэмдэгтийг яг нэг өөр тэмдэгтээр солино. Хоёр тэгийг нэгийн тэмдэгтээр солих ба эсрэг тохиолдолд тэг байна. Жишээлбэл "01010" тэмдэгт мөрд нэг өөрчлөлт оруулсаны дараа "0100", хоёр өөрчлөлт оруулсаны дараа "011" болно. Энэ нь хоёроор бага урттай тэмдэгт мөрөөр өөрчлөхийг хориглоно.

Гоё тэмдэгт мөрүүдийг тоолоход баавгайд тусал. Гоё тэмдэгт мөрүүдийн тоо хэтэрхий том байж болох тул $1000000007$ $(10^{9} + 7)$ модулиар хуваасан үлдэгдлийг хэвлэнэ.

Оролт

Эхний мөр нь зайгаар тусгаарлагдсан гурван бүхэл $n, m, g$ $(0 ≤ n, m ≤ 10^{5}, n + m ≥ 1, 0 ≤ g ≤ 1)$ тооноос бүрдэнэ.

Гаралт

Нэг бүхэл тоо хэвлэнэ. Асуултын хариултыг $1000000007$ $(10^{9} + 7)$ хэвлэнэ.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
1 1 0
Гаралт
2
Оролт
2 2 0
Гаралт
4
Оролт
1 1 1
Гаралт
0

Тэмдэглэл

Эхний жишээний гоё тэмдэгт мөрүүд: "01", "10".

Хоёр дахь жишээний гоё тэмдэгт мөрүүд: "0011", "1001", "1010", "1100".

Гурав дахь жишээнд гоё тэмдэгт мөр байхгүй.

Сэтгэгдлүүдийг ачааллаж байна...