ოლიმპიადა

დროის ლიმიტი: 4 წმ

მეხსიერების ლიმიტი: 256 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: IBSU, 2015, ზამთრის ოლიმპიადა, XI-XII


ელდარი სამუშაოდ ამერიკის ერთ-ერთ წამყვან კომპანიაში მიიწვიეს. მართალია საქმე ბევრი ჰქონდა, მაგრამ იგი უკვე ჩამოყალიბებული პროფესიონალი იყო და მისთვის მიცემულ დავალებებს საკმაოდ სწრაფად და იოლად ართმევდა თავს. ერთ დღესაც ელდარი  სამსახურში იჯდა და, რადგან საქმე უკვე გააკეთა, ფიქრებში ჩაიძირა. მას გაახსენდა საკუთარი წარმატებები პროგრამირებაში სტუდენტთა მსოფლიო ოლიმპიადებზე. მაშინ, როცა ის ამ ოლიმპიადებში მონაწილეობდა, სტუდენტებს ამოსახსნელად 8 ამოცანაზე მეტს არ აძლევდნენ და, გადახედა რა წარსულში თავის მიერ შექმნილ ცხრილს, სადაც მისი წარმატებები იყო ასახული, აღმოაჩინა, რომ v1 რაოდენობის ოლიმპიადაზე მან ზუსტად 1 ამოცანა ამოხსნა, v2 რაოდენობის ოლიმპიადაზე - ზუსტად 2, ..., v8 რაოდენობის ოლიმპიადაზე - ზუსტად 8 ამოცანა (ელდარს იმ ოლიმპიადების გახსენებაც კი არ უნდოდა, რომლებზეც ვერაფერი ვერ ამოხსნაJ).  სამუშაო დღის ბოლოს ელდარმა გადაწყვიტა ეს რიცხვები ბლოკნოტში ჩაენიშნა და მეორე დღეს, რადგან კვირა იყო და მეგობრებთან შეხვედრას აპირებდა, მათთან საკუთარი წარმატებებით ცოტა თავი მოეწონებინა. მართლაც, მან რიცხვები ბლოკნტოში ჩაიწერა შემდეგნაირად:  v11v22v88. შევნიშნოთ, რომ რიცხვებს შორის არავითარი ჰარები ან სხვა რაიმე გამყოფები მას არ გამოუყენებია, ანუ რიცხვები უბრალოდ ერთმანეთის მიმდევრობით ჩაწერა, რის შედეგადაც მიიღო რაღაც N რიცხვი. გარდა ამისა, მან ყველა vi არანიშნადი ნულების (წინიდან ნულების) გარეშე ჩაწერა და, თუ რომელიმე  vi  ნულის ტოლი იყო, მაშინ შესაბამის vii წყვილს საერთოდ არ წერდა.

მაგალითად, თუ v2=111, v3=1 და ყველა დანარჩენი vi=0, მაშინ ელდარი მიიღებდა რიცხვს: N=111213.

მეორე დღეს, მეგობრებთან ერთად კაფეში მჯდომმა ელდარმა სიტყვა ოლიმპიადებში მის მონაწილეობაზე ჩამოაგდო და თავისი წარმატებების დასასაბუთებლად ბლოკნოტი ამოიღო, მაგრამ დახედა თუ არა ჩაწერილ რიცხვს, აღმოაჩინა, რომ მისი შედგენის თანმიმდევრობა დავიწყებია. რა თქმა უნდა, იგი მიხვდა, რომ ისეთი (v1,v2,…,v8) განსხვავებულ ნაკრებთა რაოდენობა, რომელთაგანაც N რიცხვის მიღება შეიძლება, საკმაოდ დიდი შეიძლება იყოს. მაგალითად, ზემოთ მოტანილი რიცხვი N=111213, შეიძლება მიღებული იქნას, აგრეთვე, როცა v1 = 11 და v3 = 21.

ელდარს აინტერესებს, სულ რამდენი ასეთი ნაკრები არსებობს და მას ამის დასათვლელად საჭირო პროგრამის დაწერა არ გაუჭირდება, მაგრამ, სამწუხაროდ, თავისი ლეპტოპი კაფეში თან არა აქვს, ამიტომ დახმარებას თქვენგან ითხოვს.

დაეხმარეთ მას და მოცემული N რიცხვისათვის დაადგინეთ ასეთ განსხვავებულ ნაკრებთა რაოდენობა მოდულით 109+7=1 000 000 007.

შესატანი მონაცემები: სტანდარტული შეტანის პირველ სტრიქონში მოცემულია ერთადერთი  მთელი დადებითი N რიცხვი (1≤N<101 000 000).

გამოსატანი მონაცემები: სტანდარტული გამოტანის ერთადერთ სტრიქონში გამოიტანეთ ერთი მთელი დადებითი რიცხვი – ისეთი (v1,v2,…,v8) განსხვავებულ ნაკრებთა რაოდენობა მოდულით 109+7, რომელთაგანაც, ზემოთ აღწერილი წესით, N რიცხვის მიღება შეიძლება.

ორი (v1,v2,…,v8) და (v'1,v'2,…,v'8) ნაკრები განსხვავებულია, თუ ერთი მაინც i-სათვის (1≤i≤8) vi≠v′i.

ყურადღება მიაქციეთ იმ ფაქტს, რომ ელდარს ბლოკნოტში რიცხვების ჩაწერის დროს შეიძლებოდა შეცდომა დაეშვა და ისეთი N რიცხვი მიეღო, რომელიც არცერთ (v1,v2,…,v8) ნაკრებს არ შეესაბამება.




მაგალითები

შესატანი მონაცემები
111213 დაკოპირება
გამოსატანი მონაცემები
5 დაკოპირება