彼の夢は、C 市の急行列車とともに、彼が待っていた駅を轟音を立てて通過し、彼だけを置き去りにした。

C 市は $n$ 個の駅を持つ新しい地下鉄路線を開通させました。$i$ 番目の駅はレベル $1 \le a_i \le k$ を持っており、これは駅の重要度を表します。一般に、駅のレベルが高いほど、より多くの列車がそこに停車します。

C 市はこの新しい地下鉄路線で $m$ 種類の列車運行系統を開設する計画を立てています。$i$ 番目の系統には切り替え地点 $p_i$ と 2 つのレベルパラメータ $x_i$ と $y_i$ があり、その系統の列車は $1$ 番目の駅から $p_i$ 番目の駅までのうちレベルが $x_i$ 以上のすべての駅に停車し、$(p_i + 1)$ 番目の駅から $n$ 番目の駅までのうちレベルが $y_i$ 以上のすべての駅に停車することを意味します。より正確には、列車は以下の条件の少なくとも一方を満たすすべての駅 $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）のようなものです。

異なる 2 つの駅について、少なくとも 1 つの運行系統がその両方の駅に停車するとき、それらは直接到達可能であるといいます。同じレベル（$a_i = a_j$）を持つ異なる駅のすべてのペア $(i, j)$ が直接到達可能であるとき、その地下鉄路線は効率的であると呼びます。

$p_1, \dots, p_m$ と $x_1, \dots, x_m$ が与えられます。地下鉄路線が効率的となるような、$1$ 以上 $k$ 以下の正の整数からなる $y_1, \dots, y_m$ の組み合わせが何通りあるかを求めてください。答えは非常に大きくなる可能性があるため、$998\,244\,353$ で割った余りを出力してください。

入力

1 行目には、駅の数、運行系統の数、駅のレベルの上限を表す 3 つの整数 $n$ ($2 \le n \le 10^3$)、$m$ ($1 \le m \le 10^3$)、$k$ ($1 \le k \le 500$) が与えられます。すべてのレベルについて少なくとも 1 つの駅が存在するとは限らないことに注意してください。

2 行目には、各駅のレベルを表す $n$ 個の整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le k$) が与えられます。

続く $m$ 行は運行系統を記述します。そのうちの $i$ 行目には、$i$ 番目の運行系統の 2 つのパラメータを表す 2 つの整数 $p_i$ ($1 \le p_i < n$) と $x_i$ ($1 \le x_i \le k$) が与えられます。

出力

可能な配列 $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 の説明：以下は可能な構成の 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