SOLVE

LATER

Vasya and Party!

Problem

Editorial

Analytics

Today is Vasya's birthday. On this special occasion, he has organized a party for all of his friends. These friends are enumerated by integers from $$1$$ to $$N$$. Each of Vasya's friends has a **Knowledge Level**. In addition, each of them knows an arbitrary number of other people at the party. This friendship is bidirectional and transitive in nature, i.e if person $$A$$ knows person $$B$$ and person $$B$$ knows person $$C$$, then we consider that person $$A$$ knows person $$C$$. All these people who know each other come together and form a single group of friends.

Now, they decide to play a game. In this game, among all groups of friends, the one with the highest knowledge level within each group is elected to represent the group during the game. Let's call this person the leader of the group. If there are multiple candidates to be the leader of a group, you can select any of them arbitrarily. The game is then played after selecting these leaders.

Now, Vasya wants to find the number of distinct ways the game can be played. He finds this task too hard and wants you to help him. As this number can be large, print it **Modulo** $$10^9+7$$.

**Input Format**:

The first line contains two integers $$N$$ and $$M$$ denoting the number of people Vasya has invited to the party and the number of relations between these people. The next line contains $$N$$ space separated integers denoting the where the $$i^{th}$$ integer denotes the knowledge level of person $$i$$. Each of the next $$M$$ lines contains $$2$$ space separated integers $$u$$ and $$v$$ denoting that person $$u$$ knows person $$v$$ and vice-versa.

**Output Format**

Print the required answer on a single line. As the answer may be large, print it **Modulo** $$10^9+7$$

**Constraints**

$$ 1 \le N \le 10^5 $$

$$ 0 \le M \le 10^5 $$

$$ 0 \le A[i] \le 10^9 $$

$$ 1 \le u,v \le N $$

$$ M \le (N*(N-1))/2 $$

**Note**:

There can be self loops, i.e edges from and to the same person and multple edges from one person to another.

Explanation

Here, all the people at the party know each other. Among this group the person with the highest knowledge is person $$5$$. Hence, there is only one way.

Time Limit:
1.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Marking Scheme:
Marks are awarded when all the testcases pass.

Allowed Languages:
C,
C++,
Clojure,
C#,
D,
Erlang,
F#,
Go,
Groovy,
Haskell,
Java,
Java 8,
JavaScript(Rhino),
JavaScript(Node.js),
Lisp,
Lisp (SBCL),
Lua,
Objective-C,
OCaml,
Octave,
Pascal,
Perl,
PHP,
Python,
Python 3,
R(RScript),
Racket,
Ruby,
Rust,
Scala 2.11.8,
Swift,
Visual Basic

Initializing Code Editor...

OTHER PROBLEMS OF THIS CHALLENGE

{"9bcb9ff": "/pagelets/problems-hint/algorithm/vasya-and-party/", "9bcb9d0": "/pagelets/suggested-problems/algorithm/vasya-and-party/", "9bcb9a6": "/pagelets/show-submission/algorithm/vasya-and-party/", "9bcb9e9": "/pagelets/problem-author-tester/algorithm/vasya-and-party/", "9bcba14": "/pagelets/recommended-problems/algorithm/vasya-and-party/"}

{}

realtime.hackerearth.com

80

1915f7f6dd0dc947e53897cf9082bb5f84217849

58a29e5cae2309f04b28

/realtime/pusher/auth/