Problem Statement

You are given a string S consisting of digits between 1 and 9, inclusive. You can insert the letter + into some of the positions (possibly none) between two letters in this string. Here, + must not occur consecutively after insertion.

All strings that can be obtained in this way can be evaluated as formulas.

Evaluate all possible formulas, and print the sum of the results.

Constraints

• 1 \leq |S| \leq 10
• All letters in S are digits between 1 and 9, inclusive.

Sample Input 1

125

Sample Output 1

176

There are 4 formulas that can be obtained: 125, 1+25, 12+5 and 1+2+5. When each formula is evaluated,

• 125
• 1+25=26
• 12+5=17
• 1+2+5=8

Thus, the sum is 125+26+17+8=176.

Sample Input 2

9999999999

Sample Output 2

12656242944

Problem Statement

We have a grid with H rows and W columns. At first, all cells were painted white.

Snuke painted N of these cells. The i-th ( 1 \leq i \leq N ) cell he painted is the cell at the a_i-th row and b_i-th column.

Compute the following:

• For each integer j ( 0 \leq j \leq 9 ), how many subrectangles of size 3×3 of the grid contains exactly j black cells, after Snuke painted N cells?

Constraints

• 3 \leq H \leq 10^9
• 3 \leq W \leq 10^9
• 0 \leq N \leq min(10^5,H×W)
• 1 \leq a_i \leq H (1 \leq i \leq N)
• 1 \leq b_i \leq W (1 \leq i \leq N)
• (a_i, b_i) \neq (a_j, b_j) (i \neq j)

Sample Input 1

4 5 8
1 1
1 4
1 5
2 3
3 1
3 2
3 4
4 4

Sample Output 1

0
0
0
2
4
0
0
0
0
0

There are six subrectangles of size 3×3. Two of them contain three black cells each, and the remaining four contain four black cells each.

Sample Input 2

10 10 20
1 1
1 4
1 9
2 5
3 10
4 2
4 7
5 9
6 4
6 6
6 7
7 1
7 3
7 7
8 1
8 5
8 10
9 2
10 4
10 9

Sample Output 2

4
26
22
10
2
0
0
0
0
0

Sample Input 3

1000000000 1000000000 0

Sample Output 3

999999996000000004
0
0
0
0
0
0
0
0
0

Problem Statement

Snuke's town has a subway system, consisting of N stations and M railway lines. The stations are numbered 1 through N. Each line is operated by a company. Each company has an identification number.

The i-th ( 1 \leq i \leq M ) line connects station p_i and q_i bidirectionally. There is no intermediate station. This line is operated by company c_i.

You can change trains at a station where multiple lines are available.

The fare system used in this subway system is a bit strange. When a passenger only uses lines that are operated by the same company, the fare is 1 yen (the currency of Japan). Whenever a passenger changes to a line that is operated by a different company from the current line, the passenger is charged an additional fare of 1 yen. In a case where a passenger who changed from some company A's line to another company's line changes to company A's line again, the additional fare is incurred again.

Snuke is now at station 1 and wants to travel to station N by subway. Find the minimum required fare.

Constraints

• 2 \leq N \leq 10^5
• 0 \leq M \leq 2×10^5
• 1 \leq p_i \leq N (1 \leq i \leq M)
• 1 \leq q_i \leq N (1 \leq i \leq M)
• 1 \leq c_i \leq 10^6 (1 \leq i \leq M)
• p_i \neq q_i (1 \leq i \leq M)

Sample Input 1

3 3
1 2 1
2 3 1
3 1 2

Sample Output 1

1

Use company 1's lines: 1 → 2 → 3. The fare is 1 yen.

Sample Input 2

8 11
1 3 1
1 4 2
2 3 1
2 5 1
3 4 3
3 6 3
3 7 3
4 8 4
5 6 1
6 7 5
7 8 5

Sample Output 2

2

First, use company 1's lines: 1 → 3 → 2 → 5 → 6. Then, use company 5's lines: 6 → 7 → 8. The fare is 2 yen.

Sample Input 3

2 0

Sample Output 3

-1

Problem Statement

Alice, Bob and Charlie are playing Card Game for Three, as below:

• At first, each of the three players has a deck consisting of some number of cards. Alice's deck has N cards, Bob's deck has M cards, and Charlie's deck has K cards. Each card has a letter a, b or c written on it. The orders of the cards in the decks cannot be rearranged.
• The players take turns. Alice goes first.
• If the current player's deck contains at least one card, discard the top card in the deck. Then, the player whose name begins with the letter on the discarded card, takes the next turn. (For example, if the card says a, Alice takes the next turn.)
• If the current player's deck is empty, the game ends and the current player wins the game.

There are 3^{N+M+K} possible patters of the three player's initial decks. Among these patterns, how many will lead to Alice's victory?

Since the answer can be large, print the count modulo 1\,000\,000\,007 (=10^9+7).

Constraints

• 1 \leq N \leq 3×10^5
• 1 \leq M \leq 3×10^5
• 1 \leq K \leq 3×10^5

Partial Scores

• 500 points will be awarded for passing the test set satisfying the following: 1 \leq N \leq 1000, 1 \leq M \leq 1000, 1 \leq K \leq 1000.

Sample Input 1

1 1 1

Sample Output 1

17

• If Alice's card is a, then Alice will win regardless of Bob's and Charlie's card. There are 3×3=9 such patterns.
• If Alice's card is b, Alice will only win when Bob's card is a, or when Bob's card is c and Charlie's card is a. There are 3+1=4 such patterns.
• If Alice's card is c, Alice will only win when Charlie's card is a, or when Charlie's card is b and Bob's card is a. There are 3+1=4 such patterns.

Thus, there are total of 9+4+4=17 patterns that will lead to Alice's victory.

Sample Input 2

4 2 2

Sample Output 2

1227

Sample Input 3

1000 1000 1000

Sample Output 3

261790852