IOI üçün seçim

Bu gün IOI üçün seçim müsabiqələrindən biri keçiriləcək. Müsabiqə zalı $n$ kompüterdən ibarət bir sıra təşkil edir. Bütün kompüterlər soldan sağa doğru $1$-dən $n$-ə qədər tam ədədlərlə nömrələnib. Ümumilikdə $m$ iştirakçı olacaq və onlar $1$-dən $m$-ə qədər tam ədədlərlə nömrələnib.

Bizdə uzunluğu $m$ olan $a$ massivi var, burada a_i\:(1 \le a_i \le n) — $i$-ci iştirakçının oturmaq istədiyi kompüterdir.

Həmçinin bizdə uzunluğu $m$ olan, $"L"$ və $"R"$ simvollarından ibarət başqa bir $b$ massivi var. b_i — $i$-ci iştirakçının zala hansı tərəfdən daxil olduğunu göstərir. $"L"$ iştirakçının $1$-ci kompüterdən solda zala daxil olduğunu və soldan sağa doğru getdiyini, $"R"$ isə iştirakçının $n$-ci kompüterdən sağda zala daxil olduğunu və sağdan sola doğru getdiyini göstərir.

İştirakçılar $1$-dən $m$-ə qədər sırayla zala daxil olurlar. Onlardan $i$-ci b_i tərəfdən zala daxil olur və a_i kompüterinə qədər gedir. Əgər bu kompüter artıq doludursa, o, həmin istiqamətdə ilk boş kompüterə qədər getməyə davam edir. Sonra həmin kompüterdə oturur. Əgər iştirakçı heç bir boş kompüterlə qarşılaşmazsa, o, məyus olur və müsabiqəni tərk edir.

$i$-ci iştirakçının məyusluğu onun istədiyi kompüter (a_i) ilə nəticədə oturduğu kompüter arasındakı məsafədir. $i$ və $j$ kompüterləri arasındakı məsafə |i - j|-ə bərabərdir.

$a$ massivindəki ədədlər bərabər ola bilər. $(a,b)$ massivlərinin n^m \cdot 2^m mümkün cütü mövcuddur.

Heç bir iştirakçının məyus olmadığı bütün $(a,b)$ massiv cütlərini nəzərdən keçirək. Onların hər biri üçün bütün iştirakçıların məyusluqlarının cəmini hesablayın. Bu ədədlərin cəmini tapın. Cavabı 10^9 + 9 modulu ilə verin.