Cho hai số nguyên dương ~a~, ~n~. Tính ~a^n~.

Input

Gồm một dòng chứa hai số nguyên dương ~a~, ~n~. (~a, n \leq 20~)

Dữ liệu đảm bảo ~a^n~ luôn nhỏ hơn ~10^{19}~.

Output

In ra giá trị ~a^n~.

Sample Test

Input:

2 3

Output:

8

Cho số nguyên dương ~N~. Đếm xem trong các chữ số của ~N~ có bao nhiêu số nguyên tố.

Input

• Gồm một số nguyên dương ~N~ duy nhất.
  
  

Output

• In ra số lượng chữ số là số nguyên tố trong ~N~.
  
  

Subtasks

• Subtask 1 (~50\%~ số điểm): ~N \leq 10^4~.
• Subtask 2 (~20\%~ số điểm): ~N \leq 10^8~.
• Subtask 3 (~30\%~ số điểm): ~N \leq 10^{100}~.
  
  

Sample Test

Input

23452345

Output

6

Note

• Có ~6~ chữ số nguyên tố trong ~N~ là ~2, 3, 5, 2, 3, 5~.

Sin-ga-lore là đất nước giáo dục lý tưởng cho nhiều học sinh đội tuyển. Ở Sing, anh Quân nổi tiếng là một học sinh giỏi đã học ~N~ môn học. Mỗi môn thứ ~i~ anh Quân được ~A_i~ điểm. Tại đây, điểm số là một số nguyên từ ~1~ đến ~5~. Điểm trung bình của mỗi học sinh là tổng điểm các môn chia cho số môn đã học (i.e. ~\frac{\sum_{i=1}^{n} A_i}{N}~) và làm tròn đến số nguyên gần nhất (Ví dụ: ~4.4~ sẽ làm tròn xuống ~4.0~, ~4.5~ sẽ làm tròn lên ~5.0~, hay ~3.49~ sẽ làm tròn xuống ~3.0~). Vì có nhiều đệ của anh Quân sang NUS học nên trường đã tặng cho anh Quân một món quà. Trường sẽ cho phép anh Quân sửa đổi tùy ý một vài điểm số bất kì. Tất nhiên là điểm đó phải hợp lệ (tức là một số nguyên từ ~1~ đến ~5~). Hỏi anh Quân sẽ phải sửa điểm của ít nhất bao nhiêu môn học để có điểm trung bình là ~5.0~

Input

• Dòng đầu tiên gồm số nguyên dương ~N~ ~(1 \le N \le 10^5)~.
• Dòng thứ hai gồm ~N~ số nguyên dương miêu tả dãy ~A~, dữ liệu đảm bảo rằng đây đều là các số nguyên dương từ ~1~ đến ~5~.

Output:

• In ra một số nguyên không âm là kết quả của bài toán.

Subtask:

• Subtask ~1~ (~30\%~ số điểm): ~N \le 9~.
• Subtask ~2~ (~70\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

4
3 2 5 4

Sample Output 1

2

Aaron đang chơi một trò chơi video có tên là Escape!. Trò chơi diễn ra trên một lưới có ~N~ hàng và ~M~ cột:

• Các hàng được đánh số từ ~1, 2, \dots, N~ từ trên xuống.
• Các cột được đánh số từ ~1, 2, \dots, M~ từ trái sang phải.
• Ô ở hàng ~i~ và cột ~j~ được ký hiệu là ~(i, j)~.

Hai ô khác nhau được coi là kề nhau nếu chúng có chung một cạnh (tối đa 4 ô kề nhau cho mỗi ô). Cụ thể:

• Ô ~(i, j)~ kề với ~(i-1, j)~, ~(i+1, j)~, ~(i, j-1)~, và ~(i, j+1)~ nếu các ô đó tồn tại.

Mỗi ô trên lưới thuộc một trong bốn loại dưới đây, và được biểu diễn bởi một ký tự:

• .: Ô trống.
• d: Ô có quái vật.
• e: Ô cửa thoát hiểm.
• #: Ô tường.
• Nếu một ô ban đầu chứa quái vật thì sau khi quái vật đó rời đi, ô đó là ô trống. Điều tương tự xảy ra với người chơi.

Aaron muốn an toàn đến được cửa thoát hiểm. Ban đầu, Aaron có 2 HP (tượng trưng cho ~2~ máu) và bắt đầu ở một ô không phải tường. Mỗi giây, các sự kiện sau diễn ra theo thứ tự:

1. Nếu HP của Aaron ~\leq 0~, trò chơi kết thúc và Aaron thua ngay lập tức.
2. Nếu Aaron đang ở ô cửa thoát hiểm (và HP ~\geq 1~), trò chơi kết thúc và Aaron thắng ngay lập tức.
3. Aaron có thể chọn đứng yên hoặc di chuyển đến một ô kề không phải tường.
4. Sau đó, mỗi quái vật sẽ có thể chọn đứng yên hoặc di chuyển đến một ô kề không phải tường. Nhiều quái vật có thể di chuyển đến cùng một ô.
5. Cuối cùng:
   • Mỗi quái vật ở cùng ô với Aaron sẽ tấn công Aaron, giảm HP của Aaron đi ~1~. Sau đó, quái vật đó biến mất khỏi lưới.

Yêu cầu

Trước khi bắt đầu trò chơi, do mạng quá lag, Aaron phải quyết định trước chuỗi các ô sẽ di chuyển tới. Nói cách khác, Aaron cần cố định các bước đi của mình mà không biết trước chuyển động của các quái vật. Do đó, các quái vật có thể xem kế hoạch của Aaron và di chuyển theo kế hoạch đó.

Một ô được gọi là ô lợi thế nếu và chỉ nếu:

• Nó không phải là tường.
• Nếu Aaron bắt đầu ở ô đó, di chuyển theo kế hoạch của mình, và luôn thắng bất kể cách di chuyển của các quái vật.

Nhiệm vụ của bạn là tính số lượng ô lợi thế trên lưới.

Dữ liệu vào từ tệp văn bản: MECUNG.INP

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~ (~1 \leq N, M \leq 3000~).
• Tiếp theo là ~N~ dòng, mỗi dòng gồm ~M~ ký tự mô tả các ô trên lưới:
  • Ký tự thứ ~j~ trong dòng thứ ~i~ biểu diễn loại của ô ~(i, j)~.

Kết quả ghi ra tệp văn bản: MECUNG.OUT

In ra một số nguyên duy nhất: số lượng ô lợi thế.

Scoring

• Subtask 1 (~15\%~ số điểm): Chỉ có tối đa 1 quái vật trên lưới.
• Subtask 2 (~15\%~ số điểm): ~N = 1~.
• Subtask 3 (~10\%~ số điểm): ~N, M \leq 10~.
• Subtask 4 (~20\%~ số điểm): ~N, M \leq 40~.
• Subtask 5 (~10\%~ số điểm): Chỉ có tối đa 1 cửa thoát hiểm.
• Subtask 6 (~20\%~ số điểm): ~N, M \leq 2000~.
• Subtask 7 (~10\%~ số điểm): Không có ràng buộc thêm.

Example

Sample Input 1

4 5
...d.
.e#e.
..d#d
.e.d.

Sample Output 1

14

Sample Input 2

4 3
e.e
##.
.#.
.#d

Sample Output 2

6

Explanation

Sample 1

Giả sử chúng ta bắt đầu tại ô (4,5) và lộ trình được chọn như sau:

...d. 
.e#e. 
..d#d 
.XXXX

X biểu thị lộ trình đã chọn.

Với lộ trình này, quái vật tại (4,4) đứng yên và quái vật tại (3,3) di chuyển xuống ngay sau khi người chơi thực hiện bước đầu tiên.

Trước khi trò chơi bắt đầu, người chơi có 2 HP và đang ở vị trí (4,5).

...d. 
.e#e. 
..d#d 
.e.dP

P biểu thị vị trí của người chơi.

Bây giờ, người chơi di chuyển sang trái, đến ô (4,4). Tại đây có một quái vật, nên người chơi chỉ còn 1 HP. Đồng thời, quái vật tại (3,3) di chuyển xuống và lưới bây giờ như sau:

...d. 
.e#e. 
...#d 
.edP.

Rõ ràng, người chơi sẽ thua ngay tại bước tiếp theo, ngay sau khi di chuyển sang trái. Có thể thấy rằng ô (4,5) không phải là ô lợi thế sau khi xem xét tất cả các khả năng của lộ trình.

Sample 2

Do chỉ có một quái vật trên bản đồ, chỉ cần xuất phát từ bất kì ô nào đi tới được lối thoát hiểm là Aaron có thể thoát ra.

Bạn được cho hai mảng có độ dài ~n~ .

• Phần tử thứ ~i~ của mảng thứ nhất là ~a_i~ .
• Phần tử thứ ~i~ của mảng thứ hai là ~b_i~ .

Một cách chia cả hai mảng thành các mảng con không rỗng được gọi là tốt nếu thỏa mãn các điều kiện sau:

• Mỗi phần tử thuộc đúng một mảng con duy nhất.
• Số lượng mảng con của cả hai mảng bằng nhau, tức là nếu mảng thứ nhất được chia thành đúng ~k~ mảng con, thì mảng thứ hai cũng phải được chia thành đúng ~k~ mảng con.
• Với mọi ~1 \leq i \leq k~, trung bình cộng của mảng con thứ ~i~ bên trái mảng thứ nhất phải nhỏ hơn hoặc bằng trung bình cộng của mảng con thứ ~i~ bên trái mảng thứ hai.

Yêu cầu: Tính số cách để chia cả hai mảng thành các mảng con không rỗng thỏa mãn các điều kiện trên. Kết quả phải được chia dư với ~10^9 + 7~. Hai cách được xem là khác nhau nếu số lượng mảng con khác nhau hoặc nếu một phần tử thuộc về mảng con khác nhau.

Dữ liệu vào từ tệp văn bản: TRUNGBINHCONG.INP

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \leq n \leq 500)~.
• Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(1 \leq a_i \leq 10^6)~.
• DDòng cuối cùng chứa ~N~ số nguyên ~b_1, b_2, \dots, b_n~ ~(1 \leq b_i \leq 10^6)~.

Kết quả ghi ra tệp văn bản: TRUNGBINHCONG.OUT

• In ra số cách chia mảng thỏa mãn các điều kiện, chia dư với ~10^9 + 7~.

Scoring

• Subtask ~1~ (~20\%~ số điểm): ~n \le 10~
• Subtask ~2~ (~30\%~ số điểm): ~n \le 80~
• Subtask ~3~ (~30\%~ số điểm): ~n \le 300~
• Subtask ~4~ (~20\%~ số điểm): Không giới hạn gì thêm.

Example

Sample Input 1

3
1 3 2
2 2 2

Sample Output 1

3

Note

Ba cách hợp lệ là:

• Chia mảng thứ nhất thành ~[1, 3], [2]~ và mảng thứ hai thành ~[2, 2], [2]~.
• Chia mảng thứ nhất thành ~[1, 3], [2]~ và mảng thứ hai thành ~[2], [2, 2]~.
• Chia mảng thứ nhất thành ~[1, 3, 2]~ và mảng thứ hai thành ~[2, 2, 2]~.