Nice to Meet You

AtCoder

IDrelay2_i

Time2000ms

Memory256MB

Difficulty—

There are $N$ islands floating in Ringo Sea, and $M$ travel agents operate ships between these islands. For convenience, we will call these islands Island $1,$ $2,$ $…,$ $N,$ and call these agents Agent $1,$ $2,$ $…,$ $M$. The sea currents in Ringo Sea change significantly each day. Depending on the state of the sea on the day, Agent $i$ $(1 ≤ i ≤ M)$ operates ships from Island $a_i$ to $b_i$, or Island $b_i$ to $a_i$, but not both at the same time. Assume that the direction of the ships of each agent is independently selected with equal probability. Now, Takahashi is on Island $1$, and Hikuhashi is on Island $2$. Let $P$ be the probability that Takahashi and Hikuhashi can travel to the same island in the day by ships operated by the $M$ agents, ignoring the factors such as the travel time for ships. Then, $P × 2^M$ is an integer. Find $P × 2^M$ modulo $10^9 + 7$. ## Constraints * $2 ≤ N ≤ 15$ * $1 ≤ M ≤ N(N-1)/2$ * $1 ≤ a_i < b_i ≤ N$ * All pairs $(a_i, b_i)$ are distinct. ## Input Input is given from Standard Input in the following format: $N$ $M$ $a_1$ $b_1$ $:$ $a_M$ $b_M$ [samples]

Samples

Input #1

Output #1

6

![image](https://img.atcoder.jp/relay2/36cba65088d9b1224a6ce9665aa44048.png)

The $2^M = 8$ scenarios shown above occur with equal probability, and Takahashi and Hikuhashi can meet on the same island in $6$ of them. Thus, $P = 6/2^M$ and $P × 2^M = 6$.

Input #2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "Nice to Meet You",
    "description": {
      "content": "There are $N$ islands floating in Ringo Sea, and $M$ travel agents operate ships between these islands. For convenience, we will call these islands Island $1,$ $2,$ $…,$ $N,$ and call these agents Age",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "relay2_i"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are $N$ islands floating in Ringo Sea, and $M$ travel agents operate ships between these islands. For convenience, we will call these islands Island $1,$ $2,$ $…,$ $N,$ and call these agents Age...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments