حلمه، جنباً إلى جنب مع القطار السريع في المدينة C، مرّ هادراً عبر المحطة التي كان ينتظر فيها، تاركاً إياه وحيداً خلفه.

افتتحت المدينة C خط مترو جديداً يضم $n$ محطات. المحطة رقم $i$ لها مستوى $1 \le a_i \le k$، وهو ما يمثل أهمية المحطة. بشكل عام، كلما ارتفع مستوى المحطة، زاد عدد القطارات التي تتوقف فيها.

تخطط المدينة C لفتح $m$ خدمات قطارات على خط المترو الجديد. الخدمة رقم $i$ لها نقطة تبديل $p_i$، ومعاملا مستوى $x_i$ و $y_i$، مما يشير إلى أن قطارات تلك الخدمة ستتوقف في جميع المحطات ذات المستوى $x_i$ على الأقل من المحطة رقم $1$ إلى المحطة رقم $p_i$، وفي جميع المحطات ذات المستوى $y_i$ على الأقل من المحطة رقم $(p_i + 1)$ إلى المحطة رقم $n$. وبشكل أكثر رسمية، تتوقف القطارات في جميع المحطات $j$ التي تحقق واحداً على الأقل مما يلي:

• $j \le p_i$ و $a_j \ge x_i$؛
• $j > p_i$ و $a_j \ge y_i$.

دعونا ننظر في بعض الأمثلة:

• إذا كان $x_i = y_i = 1$، فستتوقف القطارات في كل محطة. يُعرف هذا النوع من خدمات القطارات أيضاً باسم الخدمة المحلية (Local Service).
• إذا كان $x_i = y_i = k$، فستتوقف القطارات فقط في المحطات ذات المستوى $k$. يُعرف هذا النوع من خدمات القطارات أيضاً باسم السريع المحدود (Limited Express) أو القطار المعياري (Benchmark Train).
• إذا كان $x_i = 1, y_i = k$، فإن الخدمة تكون خدمة محلية بين $1$ و $p_i$، وسريعاً محدوداً بين $(p_i + 1)$ و $n$. يمكن أن تكون هذه خدمة عابرة (Through Service) تتوقف في كل محطة في وسط المدينة وتسرع في الضواحي.

تكون محطتان مختلفتان قابلتين للوصول المباشر إذا توقفت خدمة قطار واحدة على الأقل في كلتا المحطتين. نسمي خط المترو فعالاً إذا كانت جميع الأزواج $(i, j)$ من المحطات المختلفة التي لها نفس المستوى ($a_i = a_j$) قابلة للوصول المباشر.

يُعطى لك $p_1, \dots, p_m$ و $x_1, \dots, x_m$. يرجى حساب عدد التخطيطات الممكنة لـ $y_1, \dots, y_m$، المكونة من أعداد صحيحة موجبة بين $1$ و $k$، بحيث يكون خط المترو فعالاً. نظراً لأن العدد قد يكون كبيراً، اطبع الإجابة بباقي القسمة على $998\,244\,353$.

الإدخال

يحتوي السطر الأول على ثلاثة أعداد صحيحة $n$ ($2 \le n \le 10^3$)، و $m$ ($1 \le m \le 10^3$)، و $k$ ($1 \le k \le 500$)، تشير إلى عدد المحطات، وعدد خدمات القطارات، والحد الأعلى لمستويات المحطات. ليس من المضمون وجود محطة واحدة على الأقل لكل مستوى.

يحتوي السطر الثاني على $n$ أعداد صحيحة $a_1, a_2, \dots, a_n$ ($1 \le a_i \le k$)، تشير إلى مستوى كل محطة.

تصف الأسطر الـ $m$ التالية خدمات القطارات. يحتوي السطر الـ $i$ من هذه الأسطر على عددين صحيحين $p_i$ ($1 \le p_i < n$) و $x_i$ ($1 \le x_i \le k$)، يشيران إلى اثنين من معاملات خدمة القطار الـ $i$.

الإخراج

اطبع عدداً صحيحاً يمثل عدد المصفوفات الممكنة $y_1, \dots, y_m$، بباقي القسمة على $998\,244\,353$.

أمثلة

الإدخال 1

4 3 4
2 3 3 2
1 2
2 2
2 3

الإخراج 1

48

توضيح

شرح المثال 1: أدناه توضيح لتكوين ممكن، $y = [2, 3, 4]$:

توضيح المثال 1

• الخدمة 1: $p_1 = 1, x_1 = 2, y_1 = 2$؛
• الخدمة 2: $p_2 = 2, x_2 = 2, y_2 = 3$؛
• الخدمة 3: $p_3 = 2, x_3 = 3, y_3 = 4$.

الإدخال 2

7 3 5
2 4 3 2 4 2 3
2 2
4 3
5 2

الإخراج 2

80

الإدخال 3

4 2 10
3 7 2 5
1 4
3 3

الإخراج 3

100