Hôm nay, ở lớp học toán, thấy giáo dạy cả lớp về phép giai thừa. Thực tế, giai thừa của một số tự nhiên \(x\) (kí hiệu \(x!\)) là tích các số tự nhiên từ \(1\) đến \(x\). Lưu ý: \(0! = 1\).
VD:
\(2! = 1 * 2 = 2\)
\(5! = 1 * 2 * 3 * 4 * 5 = 120\)

Vì đây là lớp toán nâng cao, thầy định nghĩa thêm cho cả lớp rằng: với mỗi số tự nhiên \(x\), ta có \(f(x)\) là tổng giai thừa các chữ số của \(x\). VD: \(f(123) = 1! + 2! + 3! = 1 + 1 * 2 + 1 * 2 * 3 = 1 + 2 + 6 = 9\).

Sau đó, như thường lệ, thầy bắt đầu phát phiếu bài tập và hướng dẫn giải bài, thầy viết lên bảng một số tự nhiên \(x\), và một dãy số có quy luật như sau:

\(X_1 = x\)
\(X_2 = f(X_1)\)
\(X_3 = f(X_2)\)
\(...\)
\(X_n = f(X_{n - 1})\)

Nhận thấy đây là một cơ hội tốt để kiểm tra bài, xem học sinh của mình có hiểu bài hay không, thầy bắt đầu gọi tên lần lượt các học sinh lên bảng, và yêu cầu tính cho thầy số \(X_n\) với \(n\) cho trước. Vì một phần số \(n\) quá lớn, một phần vì đa số các học sinh của thầy đều không hiểu gì, chúng rụt rè bước lên bảng, từ từ cầm viên phấn lên và loay hoay hí hoáy từng chữ. Ai ai cũng mong chờ một câu nói từ thầy: "Thôi được rồi, xuống đi em!". Nhưng chờ mãi, chờ mãi, vẫn chằng có phép màu nào xảy ra cả, thầy vẫn lặng im, học trò vẫn đứng lặng như bù nhìn.

Bỗng nhiên, một tốp học sinh từ đâu ùa vào, vác theo những bó hoa tươi thắm và một mớ quà. Thì ra, đó chính là những học trò cưng của thầy, gắn bó với thầy suốt mấy năm liền, nay đã không còn là những cậu bé, cô bé nữa, họ đã đậu vào ngôi trường cấp ba mình hằng mơ ước. Họ rủ thầy ra ngoài chụp một tấm ảnh kì niệm, thầy vui vẻ nhận lời ngay.

Nhận thấy cơ hội có 1 không 2 này, các học sinh trong lớp lén lút lấy điện thoại ra, truy cập vào LQDOJ mà nhờ các bạn giải giúp. Là một con người thân thiện, hòa đồng và hay giúp đỡ mọi người, bạn hãy giúp các học sinh 'khốn khổ' này nhé!

Input

• Dòng đầu tiên chứa một số tự nhiên \(x\) \((x \leq 10^6)\).
• Dòng thứ hai chứa một số tự nhiên \(n\) \((n \leq 10^{18})\).

Output

• Một dòng duy nhất chứa đáp án của bài toán.

Example

3
5

151

Scoring

• \(50\%\) số điểm có: \(n \leq 10^5\).
• \(50\%\) số điểm có: \(n \leq 10^{18}\).